Google navigation stuck on "Checking navigation availability"
It seems I was running the 5.0 version of google maps. I tried to search for an update on the market, but I couldn't even find the app. The most surprising thing was that using the exact search strings, I was able to find it very easy in the browser.

I downloaded the 5.2 apk, and I installed it from the SDCard. Afterwards, everything worked.