Running ubuntu 11.04 and had no issues really. You have to install the restricted AMD drivers (though "additional hardware") and then the OpenCL (stream sdk) drivers from AMDs website. The latter requires some command line and the installation actually produced some errors for me, but it works fine. Small word of warning, after installing opencl (stream SDK) the installer will reboot your system no questions asked.
If you need any help, Ill gladly help out, but I need a bit more information on the problems youre having.