There is no need to take the HDD out of your MacBook in order to format it. You can use the system DVD that came with your laptop and reinstall the OS if you want. I would still recommend going over to the Ubuntu/Apple Users forum and see if you can save yourself the trouble of reinstalling the OS.
Good Luck.
EDIT. Sorry I didn't remember that you mentioned that holding "C" with the Leopard DVD did not work.
Try resetting the PRAM by holding down command-option-p-r on startup. That might allow you to boot from the DVD.