Ok I solved the problem.
I was thinking that I didn't uninstall the previous XP from the 4th primary partition before I was trying to reinstall to the first. Something told me that there may be something left in the MBR that was confusing XP. It was looking for an XP install on a linux partition.
Through linux I formatted the MBR;
dd if=/dev/zero of=/dev/sda bs=512 count=1
Then, from the linux setup, I replaced the partitions with fdisk. Wow, Linux is the superman of operating systems; after replacing the partitions the OS still worked! To anyone trying this, you have to make sure the exact sectors are in the exact same place when you do this or linux will most probably choke.
Well, XP installer works with a clean MBR now.
Hope this helps someone out there.
Thanks for your reply profdlp. I think this may work, but XP likes to stretch itself over the whole drive and use its own "Virtual" partitions. In the past I have found it difficult to install Linux after XP on a fresh disk. If I am wrong please correct me =).