What kind of files? mp3? ogg? wma?
Happens to only one filetype?
Forget windows media player, have you tryed using a decent audio manager/tag editor? mp3 has different tag standards, are you sure all your files use the same standard (ID3V2)?