Something to consider - nVidia just released a bevy of new cards yesterday.
Their "GeForce 8600GT" is aimed at less-than-US$149, which should fit in your budget. It noticeably better than the Radeon X1650XT and GeForce 7600GT, not quite up with the Radeon X1950Pro. EDIT: Oops, if you have AGP, this advice won't help you. No GeForce 8-series for AGP. Ignore this part, rest of the advice is good.
Oh, and find a place to buy online wherever you are. "Brick and mortar" retail prices can get as high as twice the online price of parts to cover the shelf space.
I'm an ATI fan, myself, but
they seem to have at least some issues with this game that nVidia cards don't.