I had a similar problem...Macbook Pro 2 GHz Intel Core Duo, went balls to the wall and replaced hard drive with new Western Digital 500gb hard drive. Tried to boot up from the install disk and it wouldn't recognize the drive, nor give me formatting options at all.
When I opened Disk Utilities (in the upper left hand side of the screen when booting Leopard disk), I was able to see that I had indeed installed the drive but, as I already mentioned, no formatting options were clickable. The only clickable thing was "Erase" which didn't make sense to me because it was a new disk and erasing it would do no good. But after fiddling for awhile I decided to bite the bullet (there was no mention of clicking "Erase" as a viable solution to my problem in any of the forums/blogs/support pages that I could find).
I clicked "Erase" and lo and behold, the new hard drive was being formatted right before my eyes. After just a few seconds I was able to restart the computer, I held the option key to boot from disk and voila! I installed OS X Leopard on my new hard drive and am happily typing this for all those who have a similar problem. Just click "Erase" in the Disk Utility when you have the hard drive highlighted. That solved it for me!