I’d say my next step would be to see if other functions are working properly ... try to isolate the problem.  I’d recommend that you logon to your Garmin account and modify (a) a personal message or (b) add a new contact (maybe yourself if no one comes to mind).  Then power up your unit and see if it automatically sync’s to these changes.  (These changes don’t alter your message count).

dd