I have the exact same issue on my Verizon S6! It appears to be random and happens when I first reboot, let the phone sit there, if I use chrome, weather app, any app etc etc. It can do this in spurts one time after the other for two minutes or it could go 30 minutes between this occurring. I've tried several fixes like uninstalling samsung pay (since it was tues and im on verizon and timing was conincidental), clearing google play cache and data, disabling google play, installing various ad aware virus scanners (like avast avg ad aware cleaner etc) that never found an issue etc etc. One time I restarted best buy app came up and gave me a google play services error notification and I finally thought I had the culprit so I uninstalled it and rebooted..... same error came up upon restart gah!
Also I'm not completely inclined to think its related to the update as I think I got that on Sunday maybe and this only started tuesday night for me. I was thinking it had something to do with Samsung pay purely because of the timing but have not been able to prove that. So dang annoying!!!