Я как всегда поймал какой-то странный глюк...
Контакты синхронизированы с гуглом.
В "контактах" мои контакты отображаются нормально. Совершенно нормально и хорошо. В звонилки, или в СМС меседжере этиже контакты отображаются кракозябрами. При входящем звонке тоже кракозябры.
Но. Кракозябрами идут не все контакты, а где-то половина. Ради интереса удалил с гугла все контакты и заново создал 6 штук. Из них 4 оказались нормальными, а два с "кракозябрами".
Глюк был на андроиде 2 и успешно перелез на андроид 4.
UPD
Победил.
После кучи форматирований и прочих манипуляций с телефоном решил я создать второй аккаунт в гугле и перелить контакты туда. Когда делал импорт обратил внимание что у меня контактов раза в два-три больше чем есть на самом деле. Начал копать. Оказалось что в веб интерфейсе гугла есть папочка "другие контакты" и там куча контактов со сбитой кодировкой (образовались там скорее всего пару лет назад когда с помощью разных костылей делал синхронизацию гугла с win mobile и PalmOS). В общем, все удалил. Ручками поправил .cvs и залил обратно. Кажется что работает теперь...)))