After some more experiments I've found that using Ubuntu 10.04, the last working catalyst driver is 10.4.Anything newer than 10.6 will crash X on start up. 10.5 and 10.6 works but seams to lack support for textures altogether and is just horrible to look at.
I've managed to install fglrx 10.4 on Ubuntu 10.04 together with kernel version 2.6.35. It seams to be working for basic 3D though I get the feeling that the driver somehow fails to render textures on an orthographic projection when more advanced features is used.
It seams that I'm out of luck using fglrx.