AGP really might be the problem, I remember hearing about issues with these cards.

You could try disabling KMS and using the classic r300c driver in UMS mode, this might work better.