I've found the bug in the r300 swtcl path that caused this, the 3D driver uses the fragment shader to do rectangular textures, and this involves feeding the texture dimensions into the fragment shaders in constants. However the code to update those constants for new textures wasn't always getting called at the correct time in the swtcl path.
is the fix and is now in mesa master, I'll pull it into mesa 7.0.x branch and I'll probably release F8 and F9 mesa packages with fixes. This probably won't make F9 GA but the 0-day mesa update will contain the fix.
This bug has been annoying me since July 2007 so woot!!