Bizarrely low performance in Civ 4 on new laptop

So I just got a new laptop (Lenovo Thinkpad T400).
It's obviously not a hardcore gaming machine, but it's vitals are respectable:
Intel Core 2 Duo P8600 (2.4GHz)
4.00GB DDR3-1066 RAM (2 from Lenovo, 2 installed by me)
ATI Mobility Radeon HD 3470 (256MB)
Vista Business x64

Ran 3dMark06 and got a score of ~2500.

There are a few games I'd like to be able to play. One of them is Civilization IV: Beyond the Sword. However, when I run it (albeit at max settings, 1440x900) I get fairly poor performance. Like low 20s FPS.

For comparison, I can play Fallout 3 at 1440x900 with High texture setting (all others minimized except for draw distances at about middle) with similar frame rates.

Any ideas what the deal is? And why Beyond the Sword keeps triggering the UAC popup whenever I run it?

Thanks.

EDIT:
Graphics drivers are already up to date.
Also, when running it with my integrated graphics card, I get like 15 FPS (same setting except no AA instead of 4x AA). So 4x AA and FPS gained with a 256MB modern discrete graphics card? Seems like something is wrong to me.

 

4x AA will severely hamper performance, try turning that off

 

turn off AA, AA is a serious performance killer anyway.

 

Hrmm, turning off the AA gets it up to 30, which is playable, but I still get the feeling the performance should be better in general. I mean I got similar performance on a 6 year old computer (albeit a desktop). Maybe I'm just expecting too much from the Radeon 3470.

 

I am pretty willing to bet that your 6 year old computer's video card has a 128-bit or 256-bit memory ring bus. The HD 3470 only has a 64-bit memory bus, which very SEVERELY hinders memory throughput and therefore that is why AA is so bad. Your new laptop has a bus that can only put through either half or a fourth of what your desktop card can. That is why AA performs so badly.