Unlikely as this is, in case someone has the same problem as me. The only way I could fix this was to change to the xine backend for Phonon instead of GStreamer one. I should also mention that the videos I'm playing are OGV files encoded using the Theora video codec.

So this isn't specifically a QT problem but more of an issue with the Phonon backends.