I believe WAV files tend to be problematic unless they were created using the device itself (that is, recording from the microphone or the FM radio). Normally, most other formats will work without issue.
However, files with metadata (ID3 tags, VorbisComment, etc) can have problems if said metadata isn’t encoded using ISO 8859-1 characters. You can force the files to use this character format using a number of tagging programs. MP3Tag is easily the most highly recommended program on this site. Just be warned: you will need to manually set the program to use the above format, here’s how:
Click the tools menu and select Options (or press control+o). On the right, you’ll notice a a number of categories sorted into a tree-like list. Under the “Tags” heading, select Mpeg. In the “Write” section, click the “ID3v2 ISO-8859-1” option, and click OK.
Once this step is done, it will not need to be repeated. From there, load your music files, and re-save the tags. You will need to ensure that ALL audio files have been processed like so before placing them on the device. If you have files on the device that have not been processed like so, you may need to delete all of the *.dat on the root directory of the device, so that it may reprocess these file properly. Be warned: after doing so, the database refresh will take a longer time to complete than usual. In my experience, it is usually a bad Idea to reconnect the device to your computer untill AFTER the database has been refreshed.