Multimedia Resources
There seem to be a few cross-platform resources for playing video and decoding movies, some of which are available in Python. It might be worthwhile trying to create wrappers for some of the more interesting projects.
Non-Python Resources
The avifile project provides a Qt 3-based player on Linux, and would seem to be a reasonable candidate for a PyQt wrapper. However, there doesn't seem to be much documentation for it outside the header files, but it might be possible to create a reasonably high-level wrapper using SIP, and at least we know it will work with Qt's event loop.
FFmpeg provides a set of tools and libraries that could be used to play and manipulate video.
Python Resources
PyMedia is a Python package that supports various audio and video formats.
In a message to the PyQt mailing list, Baz Walter gives an example of using GStreamer bindings for Python with PyQt (see Using GStreamer with PyQt).
Out of Process Wrappers
Henning Schröder posted a link to his PyQt (Qt 3) MPlayer wrapper widget in a message to the mailing list. He has kindly donated the code to the community, and it can also be obtained from the MPlayerWidget page.