I recommend using Partition Wizard, as this tutorial explains. Partition Wizard : Use the Bootable CD
You've come up against one of the limitations of Disk Management in that it will only let you shrink a partition once.
Download the Partition Wizard file and create a boot disc with it, then boot into it to carry out your partitioning exercise, and then boot back into Windows when you're done.
As for Windows, I'd recommend 40GB for the 64-bit version, more if you are installing applications as well.