The GParted author reported the successful shrinking and moving of Vista partitions. The only problem left is that you still need the Vista DVD/CD once after that operation.
The gparted author Larry wrote a short but nice howto about the steps necessary to shrink/move a Vista partition.
All you need is the gparted live CD – and, unfortunately, the Vista DVD/CD. The reason is that Windows detects that the hardware was changed and fails to start (why is it so picky?). Therefore you have to start the repair routine of the Vista DVD/CD, but that should be no problem.
Funnily after the repair the next Windows start will fail as well – due to consistency problems of the NTFS system. I wonder why that is not repaired by the repair tool… Anyway, you are asked to run the repair tool, and you should definitely do it. Afterwards the system starts as usual and you have more space on your partition.
So now you can install Linux – but keep an eye on the boot manager difficulties.