Leopard won't install-Says to run Disk Utility

Around 4 weeks ago I started having a few problems with my MacBook Pro. For example Safari would not load, then I was unable to run Excel, etc. It seemed something got corrupted by OS X. I had a backup that was done using SuperDuper to an external hard drive and I was able to boot to that fine. I did a complete restore of my hard drive from this backup and my computer has worked fine for the previous 4 weeks.
Last night I decided to install Leopard and in case anything is wrong with my Tiger installation I decided to do a fresh install. I backed up all data to another hard drive and did a fresh install. I chose this when I put the Leopard disc in and it did a complete format of my hard drive. I expected it to proceed fine and then I get to a yellow screen with an exclamation point saying it can't install to this hard drive and to run DIsk Utility. The problem is how do I run Disk Utility when it's a blank hard drive? Can it somehow run from the Leopard or even my MacBook Pro's original TIger install disks? I can't help but wonder if it's some type of hard drive problem but yet after my issue 4 weeks ago it has worked fine. Any idea how I can get around this by running Disk Utility or anything else like that?