Kernel of the Arch Linux x64 mentioned previously:
$ uname -r
3.11.5-1-ARCH

----

As far as I know, this is not a regression. Some old live cds have the same
problem:

- Booting from an old Arch live-cd (2.6.33-ARCH) freezes shortly after modules
are loaded. Halfway down the screen, in the native resolution, it displays the
next line of booting up, and nothing else.

- When using a Ubuntu 12.04 live cd or a Linux Mint 10 live cd, there is a
black screen and the system locks up while booting. These cds, if using
'nomodeset', can get to a desktop. Switching to a VT and using 'rmmod radeon;
modprobe radeon modeset=1' makes it lock up.

----

I probably should have mentioned this in the initial comment, but the card
works fine in Windows, as well as using Linux + Catalyst.