I was having this error 495 while trying to update any existing app or download a new one from the Play store..I did notice that switching to WiFi does serve as a workaround but issue reappears as I switch back to 3G.. But I managed to resolve the issue (so far so good, dont know if it'll resurface :P)..
Here's what I did:
Menu>System Settings>Apps. Under "Downloaded", found "Google Play Services" and "Google Play Store". Opened both, "Force Stop" , "Clear Data" and Uninstall Updates/Uninstall.
Restarted the phone. Have not installed the "Google Play Services" so far, no idea how far it is necessary. But now play store is working fine. I have tried both downloading a new and update an existing, all have worked fine.
Hoping this helps. I have been freaking out for the last few days on this problem.