Hmm, odd. So what version of the Catalyst drivers are you using?
I think the latest. I used
$ sudo apt-get install fglrx
Anyway, I think this is a problem in a level more fundamental than drivers (it's supposed to list the device correctly before installing proprietary drivers).
apt-get? what are your repositories? i think to start with, i'd stick with the ati downloads, after purging everything related to the OS-installed versions of fglrx, radeon, & etc.
but yes - it's more fundamental than your drivers.
what motherboard are you using? what other hardware is hung on it? what linux OS?