Best thing to do which always works (mine periodically says No Media Found, esp on cold mornings) is to unplug the stick and plug in another with different music on, so forcing a flush and reload of the file structure.
After you plug the alternate stick in, press the voice button and say "Folders" you shoud get a "Building system library, please wait..." message.
When complete, just reinert your other stick and do it again.
Works every time. Buy a crappy 128M stick from a pound shop and just pust a few tracks on it. Keep it in the car - not ideal but at least it sorts it!
PS: I've tried a whole load of memory sticks and all have worked fine (including the one I use all the time which is a 4Gig) so I don't think there's much between them...