The 2:8.721-0ubuntu2 package for amd64 is missing the /usr/lib/fglrx/ld.so.conf and thus it doesn't configure correctly. You can fix this for now by creating that file with the contents "/usr/lib/fglrx" (without quotes) and then doing a "dpkg --configure -a". Worked fine for me.
The 2:8.721-0ubuntu2 package for amd64 is missing the /usr/lib/ fglrx/ld. so.conf and thus it doesn't configure correctly. You can fix this for now by creating that file with the contents "/usr/lib/fglrx" (without quotes) and then doing a "dpkg --configure -a". Worked fine for me.