Are you contacts' numbers saved in international format? (With the '+' and country code). If not, try changing one of the contacts who you are sure he uses whatsapp with that number, to be in international format with + sign then resync. Let me know the result.