If you need newer drivers, you could look around for PPAs in ubuntu that have them, but if you don't mind switching distros, I'd say go with a rolling-release one. Those tend to adopt upstream changes a lot quicker than versioned distros like Ubuntu and Fedora.
I'd recommend Arch Linux because they are very up to date, don't do a lot of patching, and have excellent documentation. They have this very detailed wiki page on
AMD drivers. Even if you don't want to use Arch, you might be able to find some useful information on that page.
Edit:
Oh, you said "out of the box". Don't know about that one. Maybe ArchBang? It's very up to date as well, but requires a whole lot less setting up than regular ol' Arch.
Also sorry for all the Arch-stuff, I may just love it a little too much