have the exact same issue after a firmware update, but could have been before its just that I tested all the apps after the update.
WHat I find is that if you launch Nav from within the Maps app, then it works. But if you launch it direct, then it fails.
When it launches from Maps it looks like its a new program and never run before.
so I can get it to work, but only via another program