Oh, just use the live chat on HP and ask them to kindly send you one. Just say "i'm positive a restore disc would enable me to fix this problem, but the system wouldn't let me burn one when I got it from the factory and I didn't realize it'd be a problem until now". As long as you make it sound like you tried to burn the recovery discs, but failed, they'll send you one for free (they did for me) I should mention that I legitimately tried to burn the discs but I used a Sony disc which corrupted the burn and once the hp burner thinks you've created a copy it won't let you "redo" it even if it means the first copy failed verification.
If I were at my university right now i'd happily upload the disc to you at 2.7 mbytes/sec, but unfortunately it would take a decade on dial-up.
But, I couldn't get the system to actually recover when I tried using the discs. I would get into windows and everything then it would just get stuck in an infinite reboot loop when trying to install something.
Oh I have another idea. Try installing XP on another system or using Acronis True Image to copy an XP install from another system and use the Acronis boot disc to put that already-install on your laptop. It's worth a shot...basically a heart-transplant from one system to another. It makes 0 sense why ubuntu would work but nothing related to microsoft. It's possible that you do have a BIOS virus, which is why I would suggest the XP-transplant and then quick flashing your bios using the packages available from the hp driver site.
Or or or, you try using BartPE which I think is like a bootable XP disc to flash your bios from. Sorry for the "broken" english but I only got 6.5 hours of sleep last night and I'm a 10-hour-a-night kind of guy