I called Garmin this morning, and as all above said, it's not a firmware, instead, the garmin CS guy emailed me a file to install, and fixed the problem immediately. I asked him if I can share the file, he said this file is specifically generated for me, so I can't share. But, anyone still having problems should call Garmin to get it fixed. I am glad I didn't return the GPS, or sent to Garmin to fix it.
The trade-off being getting a new unit for the return shipping cost.