Play Store

You could try going to settings--apps--all--google play services. ...once there click the clear data button and see if that provides any relief.
 
If it doesn't work, go to Android Police and download the new 4.5apk

Sent from HTC Note Ultra Pro on T-Mobile