This is not specifically a gxine problem: gxine itself doesn't handle video, and I would expect other xine-lib front ends (at least) to show the same problem.
It could be a xine-lib problem, but I suspect X, kernel or possibly proprietary graphics card taintware if you're using any. What has been upgraded recently? (/var/log/dpkg.log may help.)
Alternatively, tell gxine to let xine-lib choose which video driver, then play with the configuration - you may find that it's as simple as (for Xv) disabling video.device.xv_autopaint_colorkey via the prefs window.
This is not specifically a gxine problem: gxine itself doesn't handle video, and I would expect other xine-lib front ends (at least) to show the same problem.
It could be a xine-lib problem, but I suspect X, kernel or possibly proprietary graphics card taintware if you're using any. What has been upgraded recently? (/var/log/dpkg.log may help.)
Alternatively, tell gxine to let xine-lib choose which video driver, then play with the configuration - you may find that it's as simple as (for Xv) disabling video.device. xv_autopaint_ colorkey via the prefs window.