IMac – How to restore iMac with Time Machine

If you have some extra disk space to spare, I would recommend you to make an additional backup with SuperDuper (free for basic functionality, which is all you need in this case!):

You will create a bootable backup, from which you can then boot after you get the repaired Mac back. Test this backup by booting from it once (important) and play around a bit to see if everything feels as it should (improves gut feeling).

Then, you would use SuperDuper, which obviously also is on the backup you have just booted from, and use it to "backup" back to your freshly installed, empty hard drive.

UPDATE: To create the a recovery partition, you can use this useful hint from How can I create or recreate a Lion recovery partition?.

Upsides of this method: You can immediately boot from your external disk, where the bootable backup sits, and you do not have to freshly install Lion, then upgrade to Mountain Lion, and then restore from the Time Machine backup. Hope this helps!

Your problem is almost certainly related to partitioning on a Windows machine. You can verify this by using Disk Utility to look at the Drive, in particular the Partition Map Scheme. This needs to be GUID Partition Table but is probably MBR.

You would need to repartition on OS X, but this will need you to erase all data.