Yes I am seeing this too. I use the native contacts app. I can click on the address in the contact, which will open Google maps, then hit the menu key, directions, then the blue Nav icon to open Google navigation. Much more complicated than it should be, but it works.
I have FB linked and Google contacts linked to my phone with sync active. I even went through and joined all of my duplicate contacts. The history still does not work.
It is frustrating to see what seems to be a cool feature and not have it work!