Steam recently changed the default privacy settings for all users. This may impact tracking. Ensure your profile has the correct settings by following the guide on our forums.
I'd check the HDD for errors in Ubuntu. It may be a small filesystem error, and you won't lose anything. While your there, i'd also reccomend you back up your important data if you can, just incase it's serious.
Maybe the partition table got screwed up and XP install does actually detect the HDD but not report any free place due to everything eaten up by an unkown partition type.
Yeah, like the above's said, run a check from the live CD and see what it tells you.
The system32 folder is the most important part of Windows. You shouldn't have deleted anything in there. Like Moose said, try and use Windows Repair by inserting your XP disc and starting up your comp. You'll be able to access Windows Repair in the installation menu.
If you have multiple harddrives, take out everything except the non working one and then try installing Windows. Though I'm pretty sure you'll probably end up having to repair the partitions or something by connecting to another PC, or from the Live CD.