ATI Catalyst didn't update correctly and now can't boot

Solution 1:

Unfortunately, the only "solution" that I've seen when I had to do this (and the comments above back me up) is to re-install Ubuntu without wiping the harddrive.