I have had no problems at all so here is what I do.
All my music is stored on my computer under "my music" and managed by windows media player regardless where I got it from; and this includes iTunes, Amazon, other on-line sources, and ripped cd's..
I move all the music to a sync list in media player.
Then make sure that the SD card on the phone is the sync target and then hit Sync.
On my SD card I have created a folder called "music" and all the individual album folders go into this folder directly from the sync.
The phone recognizes them instantly.
Now I know this is simple but maybe one of these steps was missing from your process. My wife just put all her music onto the main directory on the SD card and she had the same problem you all are experiencing. I re-did it using the approach above and she had instant access.
In the past we did have similar problems but the cause was a phone hardware issue so you may check that as well.
Good luck!