Monitor says "unsupported input" when starting up for the first time.

Yes that's the problem exactly.

Try <ctrl><alt><-> and <ctrl><alt><+> to change the resolution.
You can then open the display settings and set the appropriate resolution for you monitor. The problem occurs because the EDID data being sent from the monitor suggests a higher resolution than it is actually capable of.

If the problem is in the grub boot loader, you might be able to force it to a lower resolution.

First press <ctrl><alt><F2> after the machine has apparently booted. This should get you to a text console
Log in with your username and password. Execute the following command:

sudo nano /etc/default/grub

Under the line that reads:
#GRUB_GFXMODE=640x480

add one that reads:
GRUB_GFXMODE=800x600

This is a reasonable resolution for the grub screen. Save the file by pressing <ctrl><o> and then exit the editor by pressing <ctrl><x>

You now have to get grub to use the new config file so you'll need to execute the following command:

sudo update-grub

Once it has finished you can reboot:

sudo reboot

If all is well you should be able to see the grub screen correctly. If it bypasses grub you can get there anyway by holding down the shift key just before it starts booting.

If you get the grub screen but when you start Ubuntu you get the resolution problem again, try the <ctrl><alt><-> trick again to change resolutions.

If this still doesn't work, boot in recovery mode, start X in safe mode, and see if you can change the resolution in monitor configuration that way.

If all this doesn't work we may have to write a few lines into an Xorg config file to force it to use a particular resolution. (I have this problem allways because I run two machines through a KVM switch which doesn't pass any EDID data to the computer at all.)

Chris.