No worries, I took the battery out of the laptop, waited for 30 seconds, put it back in. Same error message - Not good.
So I booted into Linux and tried to mount my Windows partition. That gave me error message about there being no SuperBlock.
Turns out my Windows XP partition was totally gone! I tried a number of commercial recovery tools, ones that you burn onto a CD and boot from. All of them claimed there was no partition information to work with, therefore there was nothing to recover.
Windows Recovery Console didn't help either, running chkdsk just told me it was impossible to recover and gave up.
I eventually found a GPL'd utility called TestDisk. I downloaded Recovery Is Possible, a freeware Linux bootable image that has TestDisk included.
Amazingly, TestDisk was able to restore a backup MFT (Master File Table) to the Primary MFT. It was then also able to rebuild the Windows BootSector.
I was still unable to boot, but at least Windows Recovery Console now saw the partition correctly. From there I was able to run chkdsk now and fix a few errors (there weren't many though) and then rebuild the Windows BootSector from the console.
Windows now boots up perfectly, as if nothing was ever wrong with it. I still have no idea what caused the BootSector and MFT to get so damaged (well, they weren't even damaged, just not there!) but I'm very glad that TestDisk managed to fix it for me.
So for all you geeks out there that may oneday have to try and recover a Windows partition from basically nothing, I hope this little story might assist you. TestDisk really is a great piece of software, better than the commercial options I tried and totally 100% free in every way.