Me pasó lo mismo, parece que va con la gpu hay muchos teléfonos a los que les pasa. Creo que incluso al Samsung Galaxy note 4 al actualizar a lollipop.
Buceando por ahí encontré una medio solución temporal:
El mapa se corrige y se ve casi perfecto cuando, estando en pantalla de ver mapa, se cambia de orientación de vertical a apaisado. si os metéis en menús y demás de vuelve a fastidiar, pero al hacer de nuevo ese movimiento de vertical a apaisado se vuelve a arreglar.
A ver si lo arreglan pronto.
a ver