OK, so this thread is a bit old, but I wanted to share a fix for this, WITHOUT disabling and uninstalling updates. You'll simply need a launcher that supports Custom Activities Shortcuts (ADW.Launcher or Nova Launcher, for example)
Long press your home screen and select a New Shortcut.
Choose Activities.
Scroll down through the list of apps and choose Maps.
From the list of actions, choose Navigation.
Voila! You've got your Navigation icon back. It's still the 'new' navigation screen, but still the icon is back