Try installing ubuntu-restricted-extras
http://www.ihaveapc.com/2011/04/how-...whal%E2%80%99/
That might not do it either, there are some dodgy wmvs around that are basically spyware. They work on WMP (possibly other media players on windows) but not linux, no matter what you do....AFAIK anyway. Its also possible to do the same trick with mkv files as well. I havent heard of any getting around, but I dont pay much attention to that sort of thing.
Not that I think your mkv or wmv files have been spywared, but its always worth mentioning.
*edit- could be DRM problems as well. DRMed files can be a right pain to impossible to play with linux.