Bumping this thread as I've just spent the day trying to resolve a similar issue and think I've identified the (or a related) problem.
EE don't send UK callerid to customers in the standard +441234567890 format (as Vodafone and most international networks do) but instead as the local UK format (i.e. 01234567890). This means when you store the number as a contact, the phone doesn't know which country it's from (and when roaming it may also not work). Now in the UK this is not usually an issue if you don't ever travel abroad. However if you do, you may find that either contacts don't work when you get there, or if they do (because the phone is trying to guess the country) when you get back they stop working or are shown as being in the wrong country.
The solution is to store all your contacts in the mobile standard +441234567890 format. Unfortunately on EE, since the callerid is sent misformated without the +44 in the first place, if you store a number when someone calls you (as just about everyone does) you'll have to manually edit every contact to add +44 and remove the 0. This is an EE issue.
