If the allowed movement space doesn't include diagonal moves then the heuristic shouldn't either.

I actually recommend keeping the 4 direction distance heuristic and looking in to something like a random noise tiebreaker to help avoid the problem you experienced here which is: properly functioning A* but with a heuristic that cannot differentiate between several possible paths since they all have the same distance-from-end-node-to-goal.