Name of sender of SMS or iMessages missing, only number shown
I just had this issue happen on iOS 10.0.2. It started after I signed out of iCloud and back in (all of my contacts are stored on iCloud). I tried some of the same things you tried, all to no avail.

In my case, I noticed that all of the old message threads showed "+1 (nnn) nnn-nnnn", but all of my contacts use the "(nnn) nnn-nnnn", i.e. no country prefix. On a whim, I edited just one of the contacts that was having the issue and added the +1 prefix to their mobile number. I switched back to Messages, and right away, not only was that message thread fixed, they all were! Then I went back to that contact, removed the +1, and everything was still fixed. An easy fix, but very odd!

Of course, if you're outside the US you may need to use a different country prefix.