If the codecs work, they would be universal. You could try updating to the latest KLite codec pack, but highly doubt it will resolve the issue. Since VLC player gets the codecs from online and is the most universal player available, if that isnt working then it isnt going to be a codec. I could see if it was only WMP, as that doesnt have a large codec library. But VLC is what is used on Linux and is the best player for the largest amounts of formats.
Well thats the problem. Most of these files are the same thing shared among various sites. At most with a file name change. Since we cant discuss such things here, since I know where this is heading, the only thing that can be said is try KLite. If that doesnt work, which I dont think it will since VLC pretty much uses that library, then you will have to wait for a better source.