Разобрался как выяснилось совсем не давно ))))) Поменял в телефонной книге на телефоне контакт, решил обновить на РНСке, стер телефон и заново подключил. Опять стала такая же фигня, сперва имя потом фамилия. Начал разбираться и выяснил следующее:
1. Привязал РНС к телефону, а не наоборот (т.е. Поиск устройств делал с телефона, а не на РНСке
2. Сортировку контактов в телефоне сделал по имени (до этого были по фамилии, при этом проверил правильно записаны контакты или нет, было правильно)
И все после этого заработало, при чем с первого раза был такой глюк, что не выводилась информация о пропущенных, принятых и набранных звонках. Переподключил телефон и все стало нормально.