I originally had trouble installing this driver because I'm using Ubuntu 8.04.1 with a Custom Kernel 2.6.26rc8. Now, I know the driver doesn't compile with 2.6.26. Everything else installed, but the dkms module failed to install.
While looking around online, I found a patch for firegl_public.c. The patch was meant to make 8.5 compatible with kernel 2.6.25, but as it turns out, it also works with catlayst 8.6. But, even after that, dkms was unable to install the module after it was succesfully built (something about an error in install.o). So I located the built fglrx.ko file in one of the /fglrx/8.501/ directories I found while using the 'locate' command. I copied that module and pasted it in /lib/modules/2.6.26-rc8-custom/kernel/drivers/char. Ran 'sudo depmod -a' and boom, fully functional fglrx driver.