If you haven't already, try this:

First, put all your songs in folders, i.e.

Depeche Mode (folder)
Leave In Silence
Lie to me

etc.

Next, make sure you check the properties of your song files to make sure they're MP3's and that they're at no greater than 192kps sampling rate.

On my 2GB cards, I got something like 350 songs on each card.

Works great