What caused it for me was the embedded id3 pictures. Any song with a picture displayed when you play it in VLC or whatever will fail to play in Soldat. The same thing happens with my really old mp3 player. Anyway, get an id3 tag editor and remove the picture and then try it.
I used this
http://www.mp3tag.de/en/download.html and right clicked the picture, removed, and clicked the save icon that has its usual floppy styled icon. I did them all individually as I wasn't sure how to make changes permanent when moving between files.
USE THE ABOVE PROGRAM AT YOUR OWN RISK. I installed it on a virtual pc, so who knows if it's clean.
