I currently have the same problem in my -02 E46 M3. Hereīs some background info:
My Nav started to act funny a couple of weeks ago. First, it thought that the car was positioned a km or so away from where I actually was (IRL...

). After trying to reset the NAV in all possible ways, including leaving the car with its engine off for a half hour and using all hidden service modes I could think of, I called BMW Emergency Service to see if I could get hold of someone with an in-depth knowledge on how to reset the NAV. They didnīt have a clue, so I decided to drop by BMW in Stockholm the morning after to try to rectify the situation (pretty annoying when the car thinks itīs a submarine, being a couple of clicks out in the ocean...

).
Anyway, later that night I stopped by a shop to return some DVDīs. I left the engine running, and when I returned to the car some 20 seconds later, the display had changed completely. It now showed a totally different menu, some strange fonts and a colorscheme created by a designer that God chose to forget all about. The whole Nav-part was completely gone! Apparently, it was some kind of emergency menu, since all other functions worked properly, albeit looking pretty strange.
So the morning after, off I went to the smiling techs at BMW and showed them the non-existing Nav and the other weirdness. They quickly concluded that the Nav CD-unit wass broken and made sure that I got a replacement the week after. They also promised that this would be a temporary solution, and promptly ordered a Nav DVD-unit (which is on a prettty heavy backlog at the moment, approximate arrival middle of january).
Imagine my surprise when I started the car in the -2 C Stockholm morning a couple of days later and the display was dead....!!! I sat there and swore oaths that nearly made the leather seats crumble and the windshield crack (Iīve already had my share of problems with the car, and felt pretty fed up). I picked up the phone and called my contact at BMW to tell them I was on my way, but as soon as the number was dialled, the display popped up, and all systems were go...! Ok, now I knew that the problem lied within the CD-unit itself, and not the display, since the exchange of the unit doesnīt involve anything more than removing the unit in the back and replacing it.
To make a long story short;
If you have "cold-starting" problems with your Nav, itīs most likely that itīs only the CD-unit acting up. Itīs a known issue with X-series and 00-01 3-series.
Best regards
Peter Gutniak