Yes, I've had almost exactly the same experience as you. I built a new AMD64 system and tracked down a used Radeon X800-GTO card for it specifically because it's said to be supported by the radeon driver. But I've had nothing but headaches with it since the beginning.
I first finally got the Kubuntu 7.04 live disk running through a bit of a convoluted process.
Add 'break=bottom' to the boot options to get it to interrupt the boot process halfway through. Then, at the command line, run 'chroot /root nano /etc/X11/xorg.conf' to edit the config. When you get the options right, just save and exit a couple of times and it will continue to the end of the boot, hopefully with a working x-server.
Anyway, after lots of googling and trial-and-error, I finally narrowed the problem down to the glx driver. As soon as I commented out that module the screen came right up. Unfortunately, that meant that there was no openGL, no 3D ability, and maybe even no DRI (haven't figured out how to determine that), but at least I had a working desktop.
My permanent Debian install has the same problem, but in addition to disabling glx, I had to switch directly to the radeon driver (as opposed to the 'ati' wrapper driver), and also had to add 'ChipID 0x54df' to my device section in order for the radeon driver to detect it correctly (you can get the ID for your card
here).
One more thing. For some reason the newest xorg versions don't work at all for me, even with the above workaround. In addition, the fglrx binary drivers also fail because they're hard-coded to only detect an older version of xorg (at least, this was true as of last week), and we have to wait until ATI updates them. So I'm currently stuck with version 7.1.0 until one of these two things gets fixed.
I can't promise that you'll have the same experience, but that's what I went through. I still don't have any 3D, and the flgrx driver has turned out to be so buggy on my system as to be unusable. I'd really love to know what to do about it myself, or if there are already any open bug reports about it. It's really frustrating.