It might just be me, I have a galaxy note 2 and my boyfriend has a HTC one m8 and whenever he calls me it says unknown caller. But if he calls right back it shows up as his contact.
Its your phone lag , make sure your contact app using your background access , if not grant it for auto start and background access , and other thing is try to copy your contacts in your phone memory ,,