Why is the phone not adding international code to a call received?

[AC Question]

I migrated from a Nexus 5 to a Galaxy S6. All my contacts are stored with their international numbers, because I travel a lot and don't want to add the country code every time i need to dial a number. Having switched to the S6 now, whenever i receive a call from my contacts, it shows up as a number e.g. 0564545679, instead of the contact name (which is stored with +966564545679).
How can i change this to be like it was in Nexus 5?