SOLVED AT LAST!!!
Ok this is what worked for me:
1 Export / backup your phone address book before anything... I did it by exporting as cv card on my SD
2 log in your att addres book website https://addressbook.att.net/ there you will find all your contacts
3 Select and delete all your contacts...