Ubuntu is so-so, I'd use Debian...
I am currently running Ubuntu Server and ran into many problems installing. I used the alternate CD because the LiveCD would not load. While trying to install the alternate CD I continually got the error that the installer could not find a system to be installed. After downloading Ubuntu Server six times and then re-burning it I found that the problem was not with the disc. I also found that if I restart the installation and do the same thing a number of times Ubuntu Server will eventually install. It seems like a random occurrence of whatever was happening. I re-installed Ubuntu Server twice and the same thing happen both times.
Even though you're new to Linux I would suggest using Debian, which Ubuntu is based off of. You can download a Minimal CD/Net Install CD and probably have no problem. Because Ubuntu is Debian based you will still be able to use apt-get to update and install. To install a GUI on Debian I believe you would type:
...but it's worth looking into the exact command if you end up going with Debian.
apt-get install x-window-system-core xserver-xorg gnome-desktop-environment
I will be switching over to Debian sometime soon. I can't wait!