Did you use it to install OS X before? Or just to run Disk Utility?
What type of CD is it? What does it say on the CD itself? Does it refer to a specific model of Mac?

Could it be that your drive needs cleaning? What is the error that you're getting? Do you have an external firewire CD drive to install with?

Again .. I think it's a partitioning error ... Your previous boot pointer was trying to boot off of Slice 5 .. You need to repoint it to Slice 3.

Can you append what Disk Utility -> Get Info displays for your disk?

Mine looks like:

Name : Macintosh HD
Type : Volume

Disk Identifier : disk0s3
Mount Point : /
File System : Mac OS Extended (Journaled)
Connection Bus : ATA
IO Content : Apple_HFS
Device Tree : first-boot/@0:3

forbin might have a good point - go to your install CD and run disk utility. then click on the 'Partition' tab and see if its been cut up at all... maybe there is an old OS9 partition sitting there somewhere?

if it has been partitioned, use disk utility to put it back into one partition, then reformat...

...good luck

ps. if you are talking about a G4 desktop machine, you could always open the case, put the drive into another mac (or even a PC) and see if you can partition / format that way... then at least you would know that the drive is ok...