Make sure that the new video card's drivers aren't defaulting to a too high refresh rate for your monitor. When I installed my 9600XT it defaulted the rate to "optimum" which it chose as very high, something like 120Hz. Many older monitors or cheaper monitors will act weird at those high frequencies. Generally it isn't good to run a monitor at the max rate is "says" it can do, especially at higher resolutions, as the image problems are likely to be worse than at lower rates. Try manually setting the refresh rate to something slower, like 75Hz or 85Hz.
Forgot to mention something (which you may already know): you must set the refresh rate for each different resolution.