All of a sudden, Maps do not register/save new Bookmarks !

I tried to save a bookmark; it saves, but when I exit the Map app and relaunch it the bookmark disappears.

Also,I tried to delete a bookmark, the same thing happens:
It is deleted while am in the app but once it is relaunched the deleted bookmark reappears.

Any solution or pointer to a solution guys?