Never had one, or even a recovery disk.
WillyP, what were you using to try to format the drive? If you booted with an OS install disc (Windows or Linux), it should be able to repartition/format the drive for you.
I got the disc utility message when I tried formatting while booted from the HDD.