After I apply those apt-gets you posted, restarted X, loog out, log in, nothing looks different. Was I supposed to config anything?
BTW, it says libgl1-mesa-experimental cannot be found.
When I try to turn on my second monitor, and apply, I get this:
Is that just the drivers are not implemented?
There are a couple of things I can think of that may help you.
First, that package that you could not install is essential to descent performance (in particular, it allows you to use Gallium 3D for OpenGL acceleration). I just verified that it is available in Ubuntu 12.04, not just Debian Wheezy. However, you need to have the universe repository enabled for it to be available. The easiest way to do that is using the Ubuntu Software Center. Go to Ubuntu Software Center->Edit->Software Sources ..., check every box under the "Downloadable from the internet" section in the "Ubuntu Software" tab of the Software Sources dialog box. Close Software Center, and do the following:
sudo apt-get update
sudo apt-get purge fglrx*
sudo apt-get autoremove
sudo apt-get install libgl1-mesa-experimental
Then reboot your computer.
Second, I suspect that your other issues may be related to having an xorg.conf, which fglrx likes but radeon doesn't need. Your monitor issue could be related to the fact that fglrx and radeon parse the monitor setup section of xorg.conf in different ways. (TLDR: radeon is standards compliant, fglrx is not.) Try removing your xorg.conf, then reboot and use System Settings->Displays (the GNOME Control Center utility) to setup your monitors. I have two monitors (both LCD but with different resolutions) running perfectly on my desktop using this method; the setup sounds very similar to yours.
ls -l /etc/X11/ | grep xorg.conf # Check to see if xorg.conf exists.
# Only move the file and reboot if it exists, otherwise its unnecessary.
sudo mv /etc/X11/xorg.conf /etc/X11/xorg.conf.fglrx0