The Issue

After upgrading my Nexus s to ICS 4.0.3 the contacts in the call log were no longer recognized. It appears that ICS is expecting a different format for the phone number than the one saved previously.

This also appeared to happen to me after restoring a backup (or migrating to a new phone) even in Jellybean (both 4.1 and 4.2)

The Solution

I made an Android application that saves all of the numbers on your phone in the right format. You can download it here (You have to turn on "Unknown Sources" under Settings>Security to install this) and source here.

If I saved you some time (and frustration), feel free to buy me a beer:

Suggested solutions on the web, and why they wern't good enough (for me)

There were some suggestions floating around:

Site URL in QR Code: