Okay - looking in the service manual:
In the icon:
No satellite mark - 2 or less satellites
Yellow satellite mark - 3 satellites
Green satellite mark - 4 or more
I always have a green icon in S. Cal.
If you've recal'd and you have a yellow or green icon - then you should take it in to your dealer. It may be set up for a different US region - where did you buy your MDX?
BTW to get into the diagnostics - turn on your ignition, press OK for the disclaimer, then press and hold the MENU, MAP/Guide and Cancel keys (in that order) for 5 seconds.
Press System Links
While it's diagnosing the system - all the links will be drawn in yellow - if everything's OK, then the connecting lines will be green, you'll get an OK and you'll hear a tone. If a problem is found, then the bad connection will be drawn in red and it'll show NG and a tone will sound.
After checking this page you need to reset the system - do that by turning your ignition key to OFF. You can then restart and come back to the diagnostics screen.
Go to UNIT CHECK
DO NOT USE FORCE DOWNLOAD
Press GPS - and it'll show you the GPS reception condition, and your vehicle position.
checks different conditions/sensors:
VSP - OFF when the MDX is not moving, ON when it is.
BACK - ON when in reverse, otherwise OFF
When any of the listed items is NG - the Nav system is bad.
Don't press Backup Clear
Turn off your ignition to reset.
If you feel at all uncomfortable doing/looking at this stuff on yor system - I'd highly recommend that you take your MDX into your dealer for warranty repair.
Best of luck.