I saw this bug and thought you might be interested in knowing about patched version of the XFree86 Xserver that has XVideo (and DRI, actually) working for Mach64 chips.
Add this line to /etc/apt/sources.list, and install xserver-xfree86-dri-mach64. It will divert the original X server and replace it with on that has been patched to include XVideo support. (Getting DRI to work will take building the kernel modules.) http://people.debian.org/~daenzer/dri-mach64-sid/ This patch will eventually be included in the regular XFree86. Frank