Is the OS X 10.5.6 disk that you're trying to install a gray-faced disk? If so, you can't use it, as that is a disk that was delivered with another Apple system, and those disks are locked to the system type they are delivered with. So if it was delived with a MacBook, for example, you can't use it to install on a PowerBook.
You'll need to use a black-faced retail version of 10.5 Leopard. Since this is a new installation on a blank hard drive, don't use the black-faced upgrade disk, as it requires OS X 10.4 to be installed to work. If you have a bootable backup, and an upgrade 10.5 disk, you could copy that using SuperDuper! or CCC to your new hard drive then use the upgrade disk.
Mac OS X 10.5 Leopard installation system requirements
Leopard is no longer available at the Apple Store but may be available by calling Apple Phone Sales @ 1-800-MY-APPLE (1-800-692-7753).
If you can't obtain a retail install DVD from Apple, look on eBay or Google the installer part numbers to possibly find at an on-line store. Here's what to look for:
MB427Z/A Leopard 10.5.1 install DVD
MB576Z/A Leopard 10.5.4 install DVD
MB021Z/A Leopard 10.5.6 install DVD (single user)
MB022Z/A Leopard 10.5.6 install DVD (5-user family pack)
Installing Mac OS X 10.5 Leopard
Mac OS X 10.5 Leopard Installation and Setup Guide
After you install the base 10.5, download & install the 10.5.8 combo update at http://support.apple.com/downloads/Mac_OS_X_10_5_8_Combo_Update
The DVD should look like this
Caution - Leopard does not support classic mode. So, if you currently open OS 9 apps in classic mode, you won't be able to do this if you upgrade to Leopard.