You're right, it is supposed to. What happens if you don't hold down C? There are other key combos you can try too, which force the boot sequence to look away from the setting for Startup Disk, or away from the HD.

Unfortunately, I forgot what they are - but Google or a helpful person here should reveal them

Have you tried a PRAM reset before CD booting? It might force the Mac to forget the Startup Disk setting.

Other thoughts- do you have an external HD or CD you could try and boot from? SCSI, or Firewire for a Pismo. USB boot is not supported.