In order to fix the issue, open the device, navigate to Settings > All Settings > Apps/Applications > Google Play services and clear all data and cache. After that, try again to download the utility. If it doesn't work, remove your Google Account (Settings > Accounts & Sync) and add it again.
