I'd try changing your resolution to 1024x768 and make sure you're running with 32bit color mode and then try.
An ATI 9000 (ThinkPad T40) was my demo machine for the game when I went out to the game mags so it should be fine.