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:

Once you have Catalyst 10-12 running, you'll need libva, libva-dev, and xvba-video packages from:

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: