Are you using standard Ubuntu or the Gnome remix? If your plan is to use Gnome I would go with the remix.
You may want to stick with the open source driver for video if possible, I do (it works really well in 13.04, so look out for that being released in less than a week).
Otherwise try:
Code:
sudo apt-get install fglrx
Let us know the output if it doesn't work.
Thanks.