Yup, latest FW on Ti. I have 1542 albums and 17821 tracks on a 1TB card, and they're all organised without issue. It's true, that they're all pre-tagged in MP3Tag and then sorted into folders. I'm sort of very OCD about this, but indeed if you haven't already tagged everything nearly, then there's likely to be issues irrespective of FW.
But here's my system:
1. Folder/genre structure
2. Inside a given folder:
3. How it looks in MP3Tag:
4. To arrange all tagging to be correct, you first need to manually tag it, and then follow this path:
You're finished. You can also do the above in bulk by selecting all files/folders via MP3Tag. It's time consuming to first to all this, but once it's done, navigation is a breeze.