If you turn on the player without the card in it, do all the files show up? Are your files MP3, WMA, or something else? With so many files, I guess you are using 96 kbps or else have very short songs? Are your songs properly tagged, or do many songs show up as unknown? If you go to folder mode(music, folders) are all your songs visible? If everything seems to work okay without the card, then turn off the player, insert the card, let the player rebuild the database, and see how the player works now. you didn’t mention when you updated the firmware. Did you format the player(using the player’s menu) after that?
I use 256 kbps for music, while others use 192 kbps. Imo using under 192 kbps results in sound quality that is inadequate. Since space is an issue for you, you should use variable bitrate to save space(decoding it might decrease battery life though compared to using a constant bitrate).
