Questo problema ce l'ho anch'io da tanto tempo, sia con la 4.5.3.2A che con la 4.5.4I. Non so se dipende dalle dimensioni della rubrica (ho 900 contatti) o da altro.
Io risolvo, periodicamente, cancellando la rubrica e importando nuovamente tutti i contatti.
Qualcuno ha una soluzione diversa?