I don't think there is a simple solution to this problem, it's a pretty classic issue with pathfinding and collisions.
A common solution is to disable collisions/solid behavior during movement. That is probably the easiest way out, and also quite effective for most people's purposes.
Otherwise, you're looking at predicting the future position of each object, and probably also a queue for each position since there can still be conflicts. I don't know how exactly to go about doing this, but there are algorithms out there, specifically the parts regarding leader following and queueing. Those articles are not for tile based movement, but any concept regarding grid coordinates can be applied to tiles as well.