The problem with this is that if I'm moving say left and down, it still won't go in the down direction until I stop moving.
This line needs some clarification. If the player starts moving down before being fully in the maze cell, he'll end up moving through the wall. The character MUST continue moving in the original direction of travel to clear the wall. That is, unless you plan on rotating the character, at which point you would be better off doing a radius collision test.
It would help if we knew more of your ultimate goals for this.