I have same problem
I got an Irish Galaxy Nexus a couple of weeks ago (my 1st smartphone and 1st Android).
All my numbers are saved in international format, ie. southern Ireland numbers like 0861234567 are stored as +353861234567 and UK numbers like 07845123456 are stored as +447845123456.
The problem arises when someone rings me and their number shows in non international format - it doesn't show the persons name from contacts.
This was never a problem with any phone I had previously - any ideas?