You never did say whether they are mp3 or wma, etc. It sounds like your wmp might be lacking the appropriate codecs for some audio files.
wmp codecs, ___
3ivx codec for mp4, & in fact probably a good idea to sift through here
AUDIO CODECS at free-codecs.com. At least if you know you have all necessary codecs, any popup saying you need to download more may be a trick! I know you said you downlded extra codecs, but just be sure you have all you need. eg: dialers are typical of what you may find with wma & asf files. They try to trick you into going to their site.