"Not enough space" on partitioning?
Ok, solution found on an old superuser question, posting here for posterity.
I just needed to defrag the thing
I got Coriolis iDefrag. I ran that on the compact setting (required restarting into it's own special mode, but no disk burning was needed). A few hours later I tried to resize the partition and it worked fine.