Is the memory card properly formatted? (There's a menu option for that somewhere, and it will, of course, erase anything and everything you already have on it.)
By default, it should have a "MUSIC" folder and a "UTILITY" folder. All songs should be in the "MUSIC" folder.
Then again, maybe it's an iTunes issue? I just use plain-Jane mp3s, and usually have no trouble. Although I have seen it refuse to play some mp3s if there is an unusual character in the filename, such as an em-dash (alt-0151), that one took me a while to figure out.
Hope that helps.