Mac OS won't install from CD, but Windows will I had to replace the hard drive in my 2010 21.5" iMac.  When I went to install the OS, I rebooted into the OS selection screen (using option).  The Mac OS X install disc was there (but my external HD, where I back up wasn't), so I selected it.

It starts by showing the Apple logo, as expected, but after a while, the logo changed to a "cannot proceed" icon (circle with a slash).  Thinking I installed the drive incorrectly, I tried my old WinXP CD.

Long story short, XP is installing right now.  I used my Mac CD trying to repair the install just before the HD failed, so I know it's readable.

Edit 1: I would like to re-iterate that the Time Machine volume doesn't show up in the boot menu either.  Shouldn't it be?

Edit 2: When I boot in verbose mode (from the CD) it works fine up until it attempts to find the "root device."  Then it just keeps repeating that it can't find it.

Edit 3: Windows successfully installed, and the BootCamp drivers installed fine, so the CD isn't the issue either.  I'm going to try Rilakkuma's suggestion and contact Apple to get an image of the last OS version I downloaded to put on a USB.

Final Edit: Never could get a USB image of the latest operating system that I purchased.  Disappointed with Apple support.  I'm just keeping Windows on here (with Bootcamp drivers).
The best way to install Mac OS X on a new drive is to clone the old drive. If I remember correctly the disk coming with Mac will not allow you to make full installation.
Installing WinXP onto the drive without BootCamp will turn it into MBR and therefore unusable for Mac OS X, so you will need to reformat it.