Each time I restart my phone the names of contacts disappear en all I see numbers. Once I call someone that particular name starts to show instead of his number. Basically if I want all names I have to start a call with everyone.
Could it be that for some reason the number displayed in the call log is in a slightly different format than the one you have saved?
I know that in my case, when a contact calls me, for some reason the caller ID for just his number displays an extra 1 at the beginning and thus, the contact name does not appear.
Happened to me as well. For me it seems as if only 2-3 people called. After a reset I have the full list of incoming/outgoing calls. Pretty unreliable.
When you restart your phone, it should sort itself out in a few minutes. One thing you might want to do is run ContactX to clean up your contacts a little bit. I've always found this helps.