I googled hard and installed lots of different packages until I found out that gstreamer-ffmpeg will do the job. Note that you might need to restart your player after installing it.
There is quite a lot of noise regarding this error in the Internet. It is being triggered by Eclipse’s (and Eclipse-based products’) SWT, whenever it tries to generate a ‘browser’ window (like the one used when you do git commit in Aptana).