To cut a long story short, after a lot of web searching and trial and error, I found the problem: my Xvideo stopped working. This was tested by typing "xvinfo" into the terminal. A healthy output would look something like this:
X-Video Extension version 2.2
Adaptor #0: "ATI Radeon AVIVO Video"
number of ports: 4
port base: 131
operations supported: PutImage
depth 24, visualID 0x23
depth 24, visualID 0x24
depth 24, visualID 0x25
And go on for quite a while (This only the first ten lines of the output when I run xvinfo.)
An unhealthy xvinfo output (and the problem I was experiencing) looks like this:
X-Video Extension version 2.2
no adaptors present
The problem with this is that I have yet to find a decent solution to "no adaptors present." I have looked and looked and looked and found very little. For one thing, if you are having problems with xvideo with fglrx, first try running (either as root or with sudo)
I have heard that for some cases this is the fix. Which is good because it is easy. But, for me, it didn't work.
After reconfiguring every option I could think of in my xorg.conf and breaking X half a dozen times, reinstalling the fglrx drivers from both the Debian repos and the binary from ati.com and breaking X half a dozen more times, the problem quite suddenly fixed itself. These are the steps that I did immediately before. I am making no claim that this will fix anything, and cannot actually describe what happened during these steps that made my xvideo work again. I say this because really, for all I know, the great Debian gods intervened and fixed it with magic. I really don't know why or even if this fixed my problem, but if you are desperate like I was, you never know. Just remember, you are trying it at your own risk.
First I downloaded the latest version of the proprietary ATI drivers. These can be found on ATI's website.
Second, I downloaded this script that I found on the Debian forums.
Third, I quit gdm and drop down to a console. This is required, the script will not run if you have any running X sessions. Then I navigated to the folder I saved these files in and (as root) ran the install script (install-fglrx-debian.sh). This will do quite a bit (and if you know your way around scripting maybe you could open the script and see. I really don't know what it did.) All I know is that it downloads a few files from the repos and installs them, downloads the ATI binary (the I already downloaded, but I'll need that one in a few minutes), and generates a package to install, then installs it. The problem with this script is that it breaks X. Why? I think it has something to do with the fact that it generated a package for me that was for Ubuntu. Whatever the case, when the script finished I tried to load up gdm and it failed.
Fourth, going back to the console, I ran (as root) ATI's file (ati-driver-installer[version number]-x86.x86_64.run) and it reinstalled the ATI driver. When gdm successfully started again, out of curiosity I ran xvinfo, but this time with success! I don't know what it did behind the screen, but suddenly I have xvideo again. I don't think it was anything in my xorg.conf (which was regenerated during this process, so back up first!) because I have nearly identical files before and after. Your best guess is as good as mine, but I've decided not to look a gifthorse in the mouth. If you are running compiz fusion, you may have to disable it to watch videos without flickering. For easy switching on/off I recommend installing the package fusion-icon and making sure it starts at boot. It makes an icon on the panel that right-clicking will allow you to switch on/off compositors and window decorators.