Pull out the hard drive, and use another computer to install bootable Ubuntu onto it. Re-install it in the notebook, and be happy.

If this sounds completely foreign to you (since MS software wouldn't be happy with a full swap like that), then don't worry: Ubuntu is fine with it.

Cheers