Running totem from command line told me the following excerpt:
VA-API version 0.39.0
Trying to open /usr/lib/x86_64-linux-gnu/dri/r600_drv_video.so
va_openDriver() returns -1
That's a sign you don't have VAAPI support in your video card driver. In my case, I have an ATI Radeon card which support VDPAU.
The answer is to remove the gstreamer vaapi package:
# sudo apt-get remove gstreamer1.0-vaapi
