iPhone cannot correctly match an incoming caller ID with numbers stored in your address book if one is in local format (without country code prefix) and the other is in international format (with +country_code prefix). Some people resorted to storing 2 numbers for each contact, but sometimes even that won't cut it.
This is a patch to make it work. Remember this is only a temporary solution, until Apple fixes it properly.
Download one of the archives below, extract AppSupport to /System/Library/Frameworks/AppSupport.framework/ and overwrite the original. Reboot your iPhone and enjoy.
As usual, backup the original AppSupport before overwriting.
the -7, -8, -9 and -10 indicates the number of digits used for matching. You should use the one that matches the length of the shortest numbers in your country. For example, if your country uses 7 digits for landline and 9 digits for mobiles, use -7.
Although this patch has been tested by many people around the globe with success, use it at your own risk and be careful when replacing original system files.
Important - Do not remove the existing file first, or rename it. This is a critical system file and the iPhone will not boot without it.