mplayer seems to play everything thrown at it, provided you set some flags in config.

VLC works brilliantly on dedicated machines and that's where I'll use it.