Codecs and Linux distros don’t mix. A few years ago, Red Hat stuff stopped playing mp3s. I love my debian Sarge desktop, but Totem just doesn’t support enough codecs out of the box. It’ll handle the basics fine and keeps in line with the minimalistic clean-lines Gnome philosophy. It just won’t handle everything that I throw at it.
Man, this thing does it all. It can stream just about everything, and it handles a lot of the Windows-based formats that other players throw ugly codec errors on. It may not be as pretty as Totem, but it sure as heck gets the job done.
Installation was cake on my Debian box. I followed these instructions but opted to install most of the related optional and suggested packages. I also went the sid route as opposed to the woody route. VLC was downloaded and installed in just a few minutes, tho I didn’t get a chance to try it out right away. Sure enough I threw some .wmv and .avi files at it and it handled them perfectly. I don’t have speakers on this box so I can’t vouch for sound decoding, but the video looked just fine.
I’d highly recommend VLC in addition to whatever media player you’re using now under Linux. There is also a Win32 and Mac OSX version. Take a look at it, I think you’ll like it.