yo optaria por probar antes otra version del Play Store, desistalando la actualizacion, forzar cierre, y rapidamente abrirla, y probar a buscar algo y ver si sale el error tambien asi,
PD: yo me he dado cuenta con los nuevos play Services 8.3.01, me da mas fallos algunas apps, como chrome al sincronizar, y hangouts, y play store (6.0.0) a veces se cierra sola tal cual, sin error alguno. estoy esperando la version nueva del sservices 8.4.89, pero para moviles 238 no ha salido