Можно экспортнуть контакты в csv, затем сменить кодировку через блокнот на utf-8 и этот файлик импортировать в gmail. Ну а уже из gmail в андроид. [Только для зарегистрированных пользователей. Зарегистрироваться.]