I have had this issue. Here is what works for me. Take the memory card out and do a battery pull/quick pull and wait for the phone to reboot. Put the memory card in when your phone is on the home page(initial screen). It will scan the media and should so all songs. If you do a battery pull and let the phone reboot with the card in it, it wont scan all the songs. I have no clue why it does that...it sucks!!
this happens to me with videos aswell what i do is I hook up my storm via usb to my pc. then make sure you use the safetly remove hardware tool once that is done you open up the media section on the phone and it will scan for new files and they should be there. This has worked for me its a pain but it works
Once you are able to see your icons and navigate through the phone, you can insert the memory card. Not during the reboot screen(white screen with clock).
i've also noticed that if you go in and delete the .dat file in the folders that contain media occasionally, it will re-scan the directory and update your library info. you will have to do this from your PC in windows explorer: go into folder options and click "show hidden folders" then go folder to folder and delete the file titled BBThumbs.dat. i do it once a week when i change my music out.
I finally got all my songs on there 1691 out of 1691 by doing a battery pull and media card insert on the white screen BUT....
For some reason it put two entire albums in the unknown catagorey i.e. unknown artist, unknown album, no artwork.
and it put 3 songs each from two other albums as just unknown artist while retaining the art and album.