Installing Fresh Copy OSX Lion on Macbook Pro

Installed a New Hard Drive. Burned a copy of OSX Lion 10.7. Loaded from the Disk.
First time it loaded from the disk and the window where it allowed you to select install OSX, Disk Utility, etc appeared.
I selected disk utility and formatted the disk for mac and continued with install.
It looked like it was going through the install fine. But after about 1/2 hr. It gave an error. Saying something like

"There was a problem installing "Mac OS X" Try reinstalling."

Now when I restart the install process. I don't get the window to select install or utility. It just starts the install process and ends with an error. I formatted the disk again but same thing happens.

How do I get around this?

Note: Now when I look at disk Utility, there is another disk partition, about 1.5GB that labeled disk2: Mac OS X Base System. (Cant' Delete it)