After a few hairy moments when neither Ubuntu nor Windows would actually boot, my re-install of Ubuntu has worked out ok.
What did I do different? Well, first of all I created a partition specifically for my /home/ directory. This is supposed to make upgrades easier since I won’t have to redo all my settings and such again.
The problem I ran into was with the famous GRUB startup menu. It wouldn’t allow me to boot to either OS, which of course is a problem.
Turns out all I really needed to do was to edit the /boot/grub/menu.lst and make sure that my linux partition was set to hd0 and windows to hd1. Then things worked out real good.
If you have similar problems, check out this thread.