I recently destroyed my Windows 7 UEFI boot sector by overwriting the corresponding EFI partition. This resulted in an error “Reboot and select proper boot device or insert boot media in selected”. This is how I fixed it (please be careful when dealing with partitioning and boot sectors, backup your data beforehand):

1. Delete what is remaining of the Windows boot partition (not the Windows partition but the partition of around 128 MB size) and the EFI partition – you can use GParted for this. In the end, you should have at least 229 MB of free space on your hard drive – preferably at the beginning.
2. Reboot from your Windows 7 DVD. Make sure you boot the UEFI part of the disk: When you open your boot menu by pressing F8, you will see two entries for your Windows 7 disk. One with “UEFI:” in front and one without. Select the former and then don’t forget to press any key if you are asked to – otherwise, the non-UEFI part would be booted.
3. When Windows starts from the DVD, select the desired language and then press Shift+F10 to open the terminal.
4. Now we will create the two missing partitions: the EFI boot sector and the Windows Boot sector. Type into the terminal (but leave the #… parts out – they are only comments by me):

   diskpart
   list disk
   select disk 0 #Select the desired disk
   create partition efi size=100
   list partition #Make sure that the 100mb partition is selected
   format quick fs=fat32 label="System"
   assign letter=B
   create partition msr size=128
   list partition #Check for errors
   list vol
   select vol 3 #Use the number corresponding to your windows installation
   assign letter=C
   exit

5. Now copy the EFI files by typing:

   mkdir B:\EFI\Microsoft\Boot
   xcopy /s C:\Windows\Boot\EFI\*.* B:\EFI\Microsoft\Boot

6. Now we will set the boot configuration data by typing:

   b:
   cd EFI\Microsoft\Boot
   bcdedit /createstore BCD
   bcdedit /store BCD  /create {bootmgr} /d “Windows Boot Manager”
   bcdedit /store BCD /create /d “Windows 7” /application osloader
   #This will return a GUID, referred to later as {guid}
   bcdedit /store BCD /set {bootmgr} default {guid}
   bcdedit /store BCD /set {bootmgr} path \EFI\Microsoft\Boot\bootmgfw.efi
   bcdedit /store BCD /set {bootmgr} displayorder {default}
   #Now it's not {bootmgr} anymore but {default}!
   bcdedit /store BCD /set {default} device partition=c:
   bcdedit /store BCD /set {default} osdevice partition=c:
   bcdedit /store BCD /set {default} path \Windows\System32\winload.efi
   bcdedit /store BCD /set {default} systemroot \Windows
   exit

7. Restart. Additionally, I had two partitions with the boot flag which also caused trouble. I changed this with GParted.
8. [Update] Configure the boot priority the UEFI menu so that the boot partition is the topmost.
9. [Update] If you still have the problem that Windows is not booting automatically (i.e. the message “Reboot and select proper boot device or insert boot media in selected” is still displayed) but everything works fine when you open the boot menu and select the Windows bootloader yourself, this is the solution which worked for me:
   1. Power off the computer
   2. Unplug your hard drive
   3. Restart the computer, watch the booting fail and then power off again
   4. Replug your hard drive, restart and watch the booting succeed!