The problem description seems very similar to the problem caused by a bug CSCuk45773, This caused When Call Manager phones are set to use the UK Network Locale. If you remove this and clear the cache of IP phone I hope this can be solved .
For more details search in bug tool kit.