Попробуйте очистить кэш Маркета: Настройки\Приложения\Управление приложениями - найдите Google Play, зайдите в него и выберите пункт Удалить данные\Очистить кэш.
Также то же самое сделайте с Google Services Framework
