Did you partition the drive using GUID? You must do this before you format it.
You can check and see by looking at the bottom left in disk utility. Under partition map scheme, it should say GUID. If it does not see GUID you need to start over.
1. Open Disk Utility in your Utilities folder. If you need to reformat your startup volume, then you must boot from your OS X Installer Disc. After the installer loads select your language and click on the Continue button. When the menu bar appears select Disk Utility from the Installer menu (Utilities menu for Tiger or Leopard.)
2. After DU loads select your hard drive (this is the entry with the mfgr.'s ID and size) from the left side list. Note the SMART status of the drive in DU's status area. If it does not say "Verified" then the drive is failing or has failed and will need replacing. SMART info will not be reported on external drives. Otherwise, click on the Partition tab in the DU main window.
3. Set the number of partitions from the dropdown menu (use 1 partition unless you wish to make more.) Set the format type to Mac OS Extended (Journaled.) Click on the Options button, set the partition scheme to GUID (only required for Intel Macs) then click on the OK button. Click on the Partition button and wait until the volume(s) mount on the Desktop.
4. Select the volume you just created (this is the sub-entry under the drive entry) from the left side list. Click on the Erase tab in the DU main window.
5. Set the format type to Mac OS Extended (Journaled.) Click on the Options button, check the button for Zero Data and click on OK to return to the Erase window.
6. Click on the Erase button. The format process can take up to several hours depending upon the drive size.
Quit DU and return to the installer. Have your TM backup drive already connected. When installing you will be provided the opportunity to restore an old system from a TM backup. I believe this will appear after completing the Setup Assistant.
If your old drive is still functional then you can put it in an external enclosure, boot from it and clone it to the new drive after the new drive has been prepped per the above.