The Recovery Disc will probably be a ghosted image of your original installation, containing all the drivers etc for the components that came with the pc. It will be useless if you change any of these, as you have found out.
You should not need a new HDD though, but as you say you will need an XP cd. Use the cd to format the drive and install XP. Hopefully all the components you have will be supported. But you will not now be able to indentify them. If its any consolation I have only ever had problems with modem drivers when installing XP, and I've done it more times than I care to remember.