It works! ... well, in principle ...

Ok, so if you are using 64-bit Ubuntu 10.04 (Lucid) and want to run Collatz on an ATI card, here is how it can be done. While it is really not the most elegant approach, it does the job.

1. Don't bother with downloading Catalyst from the AMD site, just go System > Administration > Hardware Drivers. After a search, there should be a "ATI/AMD proprietary FGLRX graphics driver". It turns out that this is Catalyst 10.4 anyway and gets rid of the issues with using .run files etc. As is also in the restricted drivers repository you will automatically get updates (time will tell if this is a good thing...)
2. Download BOINC in .sh format from Berkeley. Do not use GetDeb or the repository version, they will not work and this is what took me so long to get around. The GetDeb version should have worked as it is version "6.10.36". I used 6.10.17 which is the current recommended version. The only problem is that this worked in the middle of trying a large number of hit-and-miss options, so I have the installation on my Desktop and it requires root privileges. You may want to be a little more careful where you run the .sh file...
   
3. The only work available for 64-bit Linux/ATI is from Collatz and it is a manual install from their Power (Optimized) Application section. Read the good included "Readme" in the package if you are not familiar with where to put the library files for optimized GPU apps etc.

I still have a few things to do before this installation is complete, the most obvious one is to get the second (on-board) GPU up and running too. At this point, I think I might have a BIOS issue as the Catalyst Control Center reports it as an "Unknown Adapter"