this should happen on all radeons since radeon-rewrite. The issue here is that if texture images are specified from level 0 to some level, but if because of gl state (baselevel, maxlod etc.) the actually needed textures for rendering go from level x (!=0) to some level, miptree comparison will fail. The driver then will try to create another tree, but since it does try this only with level 0 as base it will always fail (with the error message "radeon_validate_texture failed to alloc miptree") if the calculated required firstlevel is not 0.
Note that actually there's another bug here since the fallback then always segfaults, but I didn't look at this.
I'm not actually sure what the intention of the code how to handle this is, but note that on r300 and up this should probably be fixed by not messing with the miptree at all when the required base level changes, since these chips can easily clamp both min and max levels. However, miptree changes are required for r100/r200 (which can only clamp the smallest mipmap used).