Well this is amazing. Out of desperation I moved the Virtual Machine folder back to its default location, and as if by magic XP Mode setup worked perfectly and it started. I have once again been trolled by Microsoft's products
Maguscreed, for future reference, the error was at the end of "Setting up XP Mode", that 5 minute period where it's doing installing and stuff, and would say "Windows XP Mode setup could not be completed. Please try again."