I thought it was Xine's fault for not being able to run the file properly, so I check whether there's a newer version or not, and there was so I updated, and Xine stopped working. No big deal, I had mplayer, but unfortunately it had the same old problems as Xine with that file.
Some guys suggested that the version I had of the H264 codec was compiled for a 32-bit distro, and it doesn't play well under 64-bit ones. That could be fixed with a recompile.
After some poking around at Slamd64 forums, I found some things that can help and this configure line made all the magic happen:
CFLAGS="-O2 -fPIC" ./configure --confdir=/etc --prefix=/usr --libdir=/usr/lib64 \
--with-extralibdir=/usr/lib --enable-gui --enable-largefiles \
--win32codecsdir=/usr/lib/codecs --codecsdir=/usr/lib/codecs \
MPlayer was compiled fine and worked fine, but I still have problems with that bloody video file. I tried re-encoding it using avidemux on my laptop (32-bit Kubuntu), but avidemux kept crashing.
Oh well, MPlayer works fine now, at least.