Try using SDL as the video output device. Though in fullscreen, SDL will change resolution to match the resolution of the video. For example in mplayer hit c to cycle through resolutions until the video is shown.
I think the fglrx uses xgl. Try using the radeon driver from Xorg 7.1.
For good video playback, video card software have to support XVideo or else X11 have to be used. X11 uses the raw performance of the CPU to playback video.
Use mplayer for testing because other players are glitchy when using OpenGL and SDL for video playback.
Since Beryl is OpenGL based, OpenGL needs raw performance from the video card. ATI cards are poorly supported in Linux. Only nVidia video cards have excellent support in Linux.
Go to
http://www.anandtech.com/linux/showdoc.aspx?i=2229 to get an idea of OpenGL performance of ATI and nVidia video cards.