I went to my dealer to get my nav system working right (voice feedback wouldn't shut off) again. This time the Service Advisor got Mazda on the phone and was talked through the "cold start" procedure. It fixed the problem!

"WARNING! ALL of your marked points, destinations, etc. will be gone forever when you do this!

So here is what you do:

1. Open the menu
2. Choose "setup menu"
3. Choose "system information"
4. Choose "version"
5. Push the joystick forward 3 times
6. Push the joystick rearward 3 times
7. Push the joystick forward 2 times
A new menu will appear.
8. Choose "CD check"
9. Choose "Cold start"

Yes, there are other things on this menu. I'm sure one could really mess up the nav system with them! Sadly, there is no option to get rid of the damned nag screen.