Radeon sux
J/k the brands aren't the problem, i think Nvidia and ATI are good enough for this game, i have a GeForce 4 MX440 and play fine the game, also another friend of mine who is also sticked with NVidia and is using a GeForceFX 5200.
EDIT: Check for this, go to Start Menu -> Run...
then type "dxdiag" and press enter
go to the display section
check if direct3d acceleration it's enabled, if not do it.