That's odd, I think 8.35 or 8.37 might be the version included in the restricted drivers manager in Gutsy. Give that a shot before trying the custom driver but I've had bad luck with it on a Radeon X1300.
This is what I'm running: whatever they (ATI) are saying I should on the website. And it works great, except Beryl/Compiz won't work, people said I should install XGL server first... Which seems a bit too heavy to me.
And since I have very little time to experiment with my workhorse, I decided to wait for "native" support.
Ah, yes, you need XGL, ATI does not yet support AIGLX (or the other way around). XGL works great in Gutsy, it installs easily (apt-get xserver-xgl). The problem is that OpenGL doesn't seem to work under Xgl so you either get 3D apps or a 3D desktop for now. Wait a little longer. I'd like to get off Xgl as well since it's not very stable yet.