Das sieht weniger wie ein Fehler der Heuristik und mehr wie ein Problem deiner A*-Implementierung aus. A* findet optimale Wege, wenn die Heuristik (wie die von dir verwendete) bestimmte Bedingungen erfüllt (sie darf die Kosten nie überschätzen).

Den Fehler zu finden wird aber deine Aufgabe sein, eine Black-Box zu debuggen ist quasi unmöglich ...

mfG
Markus