PowerMacs sometimes do not like changes in hardware configuration, and need a PRAM zap or CUDA-button reset to get along with the new hardware. This isn't supposed to be needed, but it does work sometimes to fix odd boot/recognition problems.
Try jumpering as Master/Slave, press and hold the CUDA button for 10 seconds, then boot up. Give Disk Utility another try at formatting. While you have Disk Utility open, check the HD's SMART status for the heck of it, see if the drive reports internal errors. I think the SMART readout only appears in OSX 10.3 Disk Utility, but it's available in Alsoft's Disk Warrior 3.x under earlier versions of OSX.
Notes:
Verify/Repair[Permissions] only apply to formatted drives. Until the drive is successfully formatted, those buttons will remain dimmed out.
The normal configuration this model shipped with was one internal HD jumpered as Single. Cable Select is not supported on this motherboard. Master/Slave is supported.
You can do a PRAM Reset (Parameter RAM - aka BIOS reset in PCese) by holding Apple+Option+p+r during startup until you hear several beeps. You may need to reset a few hardware preferences afterwards, like the system clock and default boot drive.
The CUDA button (aka the PowerManagerReset button) has been in various places on Mac motherboards. Usually it's near the battery, here is a pic of it in a G4 350 AGP which should be identical to your motherboard:
A CUDA reset is considered more serious medicine than a PRAM reset. You will have to reset the system clock and possibly other preferences afterwards.