Oh man I just went through a bunch of junk with the same problem. What I ended up doing was:
1. Reboot another computer off your install CD
2. Put the computer you want to reinstall into target disk mode (hold down the T key after the chime, then let up on it once you see the firewire symbol)
3. Connect the computers using a firewire cable
4. On your 2nd computer, start the install process and when it asks which drive, target the drive that you want to reinstall.
5. Go through the install process, then reboot when it tells you to reboot
6. It'll reboot your 2nd computer, using your formatted computer as the hard drive it's booting off of.
7. Login and go through the process, then make sure and run Software update and install all the updates.
8. When you reboot again this time it'll reboot as your regular drive, go ahead and drag the external computer hard drive into the trash, then hold down the power key on the computer with the firewire graphic flashing on it, then unhook the wire from the computers.
9. Reboot your formatted computer and you should be good to go.