Well...indeed it was the NAV drive that needed to be replaced. The dealer was great. He showed me an alert from BMW that basically said "don't replace the NAV drives when customers report this problem because it is a software issue". But it absolutely was the drive, and the dealer took the liberty of ordering me a new one and not bothering to go through the back and forth with NAVTEQ before providing me with a solution. This drive is also superior to the one that the car was built with only recently in May 2005; surprised that BMW uses up all the old inventory before going with the most updated versions.