So I'm trying this again, but now with Debain (so I don't have to worry about Ubuntu's compatibility issues with ATI legacy drivers).
Unfortunately I'm having an issue that doesn't seem to exist...
I'm missing libatiuki.so.1
My first problem is that I'm not even sure where it should go.
My second problem is that it doesn't appear to be in the debian repositories.
I'm on Wheezy and I'd rather not upgrade to Jessie(which has steam in it's repository) unless it's relatively stable.
Unless someone knows of another option...