Comment 4 for bug 1080612

You have to run:
sudo amdconfig --initial -f
after you install the fglrx-* packages.

If it still doesn't work you might need to additionally run this:
sudo amdconfig --px-dgpu