I had the same problem with Identification of incoming calls which displays a message of "Unknown number" even when the number was in my contacts.
Let me told you how I fixed the problem:
I went to ICE (In Costa Rica is a Government entity in charge of bring GSM and 3G services like AT&T and Verizon), and they change my old Sim Card (GSM of 2003 ) for a new one and that's it problem solved.
So if you want to fixed change your Sim Card and tell the Company which provides you the phone services that you need to activated the Identification of Incoming calls service.
It works for me I hope it will works for you too.