For me, it first stated happening when I updated mesa. But now it seems to
happen at random.

BTW I have managed to get the GPU to reclock again by booting with fglrx and
running Unigine Heaven till I hear the fans spin up. After I then reboot to
radeon I have got it to reclock again. This combo has worked for me three of
three times now.

At first I just thought that simply bootin with fglrx solved it. But as that
didn't work 100% of the time, I thought that perhaps simply booting with it was
not enough.

However the test pool size is quite small so I might just have gotten lucky so
far with the Heaven method.

Can you check if you get the same result, but with windows?