Most likely reason is that you have forgot to remove one of packages from the newer fglrx. Below is the instruction how you can see what are all packages intalled by fglrx and also how to check if any of files provided by fglrx is still in system after uninstall.
1. uninstall all fglrx packages listed in:
2. Get the list of files for all of those packages from that website (click the package name and scroll to bottom)
3. Copy and save the list to a text file (say fglrx_file_list_<package>)
4. save follow script to same directory with name check_files.sh and give execution permission.
5. run to see if any file are still system
if [ -e $1 ]; then
echo file $1 exists
6. Check if your current kernel still has fglrx kernel module installed
cat fglrx_file_list_* | xargs --max-args=1 ./check_files.sh
After all that seems to be clear then there is only left files that are created by installer script which I don't kno how to check for easily.
find /lib/modules/`uname -r`/ -name "fglrx*"