I think I understand how to make pushing work correctly. Instead of checking to see if a guy will end up in an impossible place then deciding to not move that guy, I now successively check each tile between the guy and the intended destination. If a guy at (0, 2) can get to tile (3, 2) on the way to the (7, 2) but can't go any further, then I just move him to (3, 2).
In order to not make the pusher not move right behind the pushee (which was the right behavior when you could only push something one tile), I had to pass information about how the pusher was moving to the push behavior.