VLC works perfectly well on Linux. But, I've also found that MPlayer works just as well.
Either one can require some tweaks if you're going to play some really high-bitrate h.264 files. But otherwise, they play everything I throw at them. Both are modable as far as skins, too, if that's a concern.
Guys just as a heads up, be careful with VLC. It's got multi-platform security leaks if you use subtitles at all I've dealt with 2 Linux and 1 windows installation this month because of it. You can read more specifics here