If your hardware specs are like mine (Intel/ATI Radeon HD 5650, switchable graphics), then know that the fglrx driver currently does not support systems with switchable graphics, and not much can be done about it now since the driver is proprietary.
Your only option is to use the open source radeon driver (which currently doesn't support 3d acceleration AFAIK), or wait until fglrx is updated to support switchable graphics.
UPDATE
AMD has released an updated driver
(11.5 as of this edit) that finally supports switchable graphics. I highly recommend using the instructions for your version of Ubuntu.
I used the instructions for 11.04 Natty and Catalyst 11.5 and the installation was smooth and successful. I suggest reading the page thoroughly before proceeding so that you know how to recover in case something doesn't go well.