I must correct myself: radeonhd works fine, only the radeon driver fails.
I originally first removed the fglrx driver, rebooted, radeonhd was autoselected (and failed), uninstalled radeonhd and while doing so noticed that I forgot to remove some fglrx-mesa-stuff. After removing both packages I tried radeon and it failed as described above. Now I re-added radeonhd and everything seems to be fine, looks almost better than the fglrx driver at the first glance.
I must correct myself: radeonhd works fine, only the radeon driver fails.
I originally first removed the fglrx driver, rebooted, radeonhd was autoselected (and failed), uninstalled radeonhd and while doing so noticed that I forgot to remove some fglrx-mesa-stuff. After removing both packages I tried radeon and it failed as described above. Now I re-added radeonhd and everything seems to be fine, looks almost better than the fglrx driver at the first glance.