Download and use this Ubuntu Boot-Repair program, or burn an Ubuntu boot-repair Disk
I had the above problem installing Ubuntu 12.10 and 13.04 on a brand new (as of November 2013) gateway computer and got this error:
Reboot and Select proper Boot device
or Insert Boot Media in selected Boot device
I was able to repair the boot loader that caused this problem.
This Ubuntu boot-repair tool can repair frequent boot issues you may encounter in Ubuntu like when you can't boot Ubuntu after installing Ubuntu. Or you can't boot Windows after installing a Linux distribution, or when you can't boot Ubuntu after installing Windows, or when GRUB is not displayed anymore, or some software update or hardware upgrade breaks GRUB, etc.
Four options. Either boot into the LiveCD and download the program and apply it to your boot loader, or create a Ubuntu OS install boot disk with boot-repair, or boot into a barebones boot-repair liveCD, or a boot repair USB stick.
What I did was boot into the Ubuntu LIVE CD and connected to the internet, then visit the following link: https://help.ubuntu.com/community/Boot-Info
Follow the directions there to install the boot repair program and accept the defaults to rebuild and restore the boot loader. For me accepting the defaults made it so I could boot into Ubuntu again.
Instead of downloading from a live CD, you could burn a boot Repair Disk which also handles LVM, GPT, separate /boot and UEFI dual boot: https://help.ubuntu.com/community/Boot-Repair
LighterWeight (Lubuntu based) Boot-RepairCD: http://sourceforge.net/projects/boot-repair-cd/files/
Full Ubuntu 13.04 liveDVD or USB Install with Boot-Repair included (for newer computers): https://help.ubuntu.com/community/LinuxSecureRemix
For info on UEFI boot install & repair: http://ubuntuforums.org/showthread.php?t=2147295
So either pitch in and help the developers figure out why that version of Ubuntu isn't working with your hardware, or troubleshoot what is wrong by learning about how the boot process works, or try a different version of Ubuntu on a different hardware.