Comment 7 for bug 566437

I solved my problem by this solution
http://forum.ubuntuusers.de/topic/nach-upgrade-fglrx-laesst-sich-nicht-deinstal/2/#post-2468538

Basically by deleting the entries from this file "/var/lib/dpkg/diversions" (can be there more than one time)
/usr/lib/libGL.so.1.2
/usr/lib/fglrx/libGL.so.1.2.xlibmesa
xorg-driver-fglrx

than the removal works:

sudo apt-get --purge remove fglrx-kernel-source fglrx-modaliases xorg-driver-fglrx fglrx-amdcccle libamdxvba1