I think I fixed this. My idea of getting to the SMS file DB put me in the right track, and then I started to think that such file could be corrupted. And so I decided to delete ALL my messages. At least that beats the one about Resetting the Phone to Factory...
Fortunately, there is a great tool to backup and restore SMS tool at Google Play store:
https://forums.androidcentral.com/e?...token=rzy4zrUN..
I got it from forum:
http://forums.androidcentral.com/ver...es-stored.html
And so, after a backup. I decided to delete all my SMS. After that I was able to start conversations again with new contacts !!!
Now I am in the process of restoring. Hopefully the new SMS DB file will be in better shape, but if not. I guess deleting the messages will do. I will update my results.