It sounds like when you installed Ubuntu you installed the boot loader to the /boot folder rather than the master boot record. The, when you deleted/formatted/pooched your ext*/Ubuntu partition you effectively blew away your bootloader. Which is why it would error out.
You can either run the "fixmbr"/"fixboot" from the Windows XP CD. (Should you find one) You can also run through the procedure to reinstall the boot loader to the master boot record. (Google that one, its a bit more involved) Or, reinstall Ubuntu. (Which will do the last mentioned step)
Although now that I think about it you may need an active ext2/3 partition in order to install the GRUB. (Or LiLO if that's your poison)
In short, just (re)install whatever Linux OS you want to try (taking care not to blow away XP) and you'll be fine.