I had a similar issue, where my shards would take forever to relocate when the cluster is grown or shrunk, flushing all shards via /_flush solved the problem for me.
Doesn't it take make sense to flush the shard before trying to replicate it somewhere? I had shards with translogs over 1gig?