I can think of a few possible explanations:
1. Did you hold C long enough? You shouldn't release it until you see the Apple logo and then you must be patient because it takes considerably longer to boot from the CD than from the hard drive.
2. Are you using a system disc that came with a different computer? If that's the case, it won't work. You need either the disc that came with your computer or a generic (black label) disc. Also, you cannot (generally speaking) boot from an OS version that is earlier than the one that was originally installed.
3. Have you tried invoking the Startup Manager? Insert the CD and reboot while pressing and holding Option. Release the key when you see a choice of startup discs, select the CD and press Return
You can run the equivalent of Disk Utility's Repair Disk without the CD by running fsck in Single User Mode. Start up while pressing and holding Command and S simultaneously. Release the keys when you see writing on the screen. After the writing has stopped loading, type
/sbin/fsck -fy (leave a space between fsck and -fy) and press Return. When finished, type
reboot and press Return.
Here's a caveat: The link that I provided is slightly inaccurate in its information about how to access Disk Utility. For a better description that takes into account OS differences, read
Mac OS X - Using Disk Utility to Repair a Disk. If you are using 10.6, the procedure is the same as for 10.4 and 10.5.
