Skylines, it's not pretty.
First, you'll need to install the latest Catalyst. Follow the removal procedure to get rid of your old driver first. Then follow the manual installation guide: http://wiki.cchtml.com/index.php/Ubu...allation_Guide
Once you have Catalyst 10-12 running, you'll need libva, libva-dev, and xvba-video packages from: http://www.splitted-desktop.com/~gbeauchesne/
After that, you'll need to find a way to rebuild VLC (or another vaapi-enabled player) against the new libraries. There is a PPA that does a lot of the heavy lifting, but I do not know if it works: https://launchpad.net/~ed10vi86/+archive/video