I have the exact same problem of flickering as described in bug #496979, with a Radeon 7500 and XVideo. Problem also solved by using the xshm driver in xine, or the x11 driver in mplayer.