I had the notification set to all contacts. At one point, I removed a single contact from the list, automatically changing it to "selected contacts". I later re-added the contact, but did not reset the selection to "all contacts". Hence, new contacts were not added by default. My bad!
/ 
