Mmh... I tend to notice a slowdown too at boot time when there are Linux partitions on my Win2K box... But that's one minute instead of thirty seconds, roughly, not TWENTY !
(I suppose because Windows tries to figure out its stuff during the delay).
You can indeed try preparing your Linux partitions with Partition Magic, that's what I usually do and never had any problem. Also, make sure you de-assign any letter to the drives you'll eventually convert from Windows before you proceed, just to be sure.