It's sounding to me like it could actually be a problem with the Radeon 2600 driver. Which one are you guys using?
I'm not sure but I thought there were two different ones? A closed source and an open source one? You could give the other one a go and see if anything changes.
I am running an Nvidia 7900GTX and have no problems like this with DoW, the only real problem I have is the mini-map fog of war doesn't always display correctly (which is a fairly minor thing to me). On the other hand I have texture striping in UT2004 (the native linux version), so the Nvidia driver isn't without its problems thats for sure (and this is a known issue with the driver).
Is there anyone else out there having these problems (or not) so we could pinpoint if this happing just with ATI cards (or specific driver) or if this is happening on some Nvidia cards too? This will help determine if the problem is driver based or elsewhere.