I haven't used Partition Magic, but I have done this with the GParted Live CD. Basically, the steps are as follows
1) Turn off Hibernation and Virtual Memory (these create unmovable objects during defragmenting/resizing)
2) Defragment hard drive
3) Reboot into partitioning tool (GParted or Partition Magic)
4) Shrink XP partition to desired level
5) Reboot into XP (let it run disk check on startup if it wants to)
6) Re-enable Virtual memory and/or hibernation
7) When you're sure everything is working, reboot into Ubuntu CD.
8) When it asks where to put Ubuntu, say "free space" at the end of the drive
That's about it. If there's nothing important on the virtual Ubuntu install, then you can nuke it ahead of all of this. That'll give you some more free space on Windows. I would guess that 10GB is fine for now. Later you may decide it's not enough if you start using linux exclusively. Typically, on my machines, I reserve 10 GB for root and then put /home on it's own partition so that I can reinstall without messing it up too badly.