first i hope your new drive is mac compatible as thats very important
http://forums.xlr8yourmac.com/drivedb/search.drivedb.lasso
i assume you got the grey discs so put it into the drive when osx is running and press install
that should work too
i hope you have pressed the "c" long enough right from startup not later at some point as its surprising how long that takes to has effect , basically you absolutly need to hold down the key already before hitting the start button and hold it until something is happening if really nothing then
try booting to open firmware (Apple-Option-O-F) and passing the command:
0> boot cd
Or, if that doesn't respond/work, try:
0> boot cdrom
Or, if that doesn't respond/work, try:
0> boot dvd
Those may force the computer to poll the cdrom/optical drive for bootable volumes
but when i reinstalled tiger on my eMac it took me about 20 attempts with the c key to get it booting...maybe a safety feature to make sure you really want to reinstall..dont know