diskutil: The partition cannot be resized but there is plenty of space

This is the error I get: The partition cannot be resized. Try reducing the amount of change in the size of the partition.

First of all, this is really not a helpful message. Why can't diskutil tell me how much change I need?

But worse of all, there is plenty of space. Situation before the resize:
* disk size: 1TB
* GUID partition table
* one partition using all disk
* the partition has a HFS+ volume with about 360GB occupied

Now, using Disk Utility I want reduce the partition to 500GB. It tells me that (after the resize) there will be 222GB space available. When I select Apply it starts to process. First it takes a looooong time to verify (the disk?, the partition?). And in the end it comes up with this famous error. "Try reducing the amount of change in the size of the partition.". Huh? Why?

Let me also say that the HFS+ volume is used for TimeMachine. But I have been careful to stop TM, I even tried after a reboot, and I even tried using Disk Utility from the installation DVD. And all the time it gives me that same error message. OK. I haven't tried to change the resize amount, because I simply don't know how much. And it is really not an option to just try, because it takes forever. Live is too short.

Has anyone successfully resized a partition with a HFS+ volume on it AND used for TM?