Did you replace the fan, or the whole cooler?
Might be worthwhile taking it off, removing the shim, cleaning the heatsink and replacing the crappy thermal tape with some nice arctic silver. It'll help the heat conductivity and might get rid of the problem if it's a heat issue.
<b>Radeon <font color=red>9700 PRO</b></font color=red> <i>(o/c 332/345)</i>
<b>AthlonXP <font color=red>3200+</b></font color=red> <i>(Barton 2500+ o/c 400 FSB)</i>
<b>3dMark03: <font color=red>5,354</b>