You need to remove Vista first...
Microsoft does not support 'downgrading' an operating system, so you will have to erase your hard drive, or at least that partition, before you can install Windows XP on it. The 'hard drive not found' issue adds an interesting twist (I'd blame the Gateway OEM recovery system's design for not being able to handle this situation) but it should be taken care of relatively easily. First, backup all files, favorites, etc. that you want to keep. Second, use DBAN to wipe your hard drive clean. (This will permenantly delete all files on the hard drive, so verify your backups before proceeding.) Once the drive has been erased then try installing Windows XP again from scratch.
Hope this helps,