This is an issue I noted when I first tried Debian Wheezy. Tonight my daughter was fixated on watching "Five Little Monkeys", which of course just happened to be an MP4 file. Totem wouldn't play it. I downloaded VLC and that would, but later I decided to see if I could track down the problem.
I found this post on the Ubuntu forum pointing to a Launchpad bug: it seems the problem has been fixed in Ubuntu. I don't know how quickly bug fixes make their way from Ubuntu to Debian, but at least there are some workarounds available: the easiest one obviously being to install VLC.