Make sure that you hold down Command + R immediately after you press the power button and not let go until you get to the menu screen with Disk Utility.
If that still doesn't work, you could try the same method but just hold down the Option key until you see hard drive icons appear on your screen. From there, insert the grey-colored CD that came with your Mac into the optical drive. This disk contains the OS that came on your Mac. Once the disk has been read, it should appear as an icon on your screen. If it doesn't appear, shutdown your Mac and turn it on again, holding the Option key down. It should appear. Once you see the CD icon, click on it and the Mac will boot directly from it, allowing you to re-install the OS.
I hope that made sense. Please feel free to ask for any clarification.
Good luck!