"Check Your Connection And Try Again" repeated toasts For about a month and a half my Nexus 6P (running Android Marshmallow 6.0.1) has at random times shown a toast of &quot;Check your connection and try again&quot;. This toast shows up no matter what app I am in, maybe two or three times a day, usually; so far today, however, my phone has given me this toast maybe 15 times.
When it shows up, I am usually actually connected to WiFi or Cellular (the issue has occurred on multiple wifi networks and multiple carriers), and loading a webpage immediately before/after it pops up invariably works. Here's what the toast looks like:


When it happens more The issue occurs more frequently (but not at all exclusively) when:

I'm downloading/updating an app from the Play Store
Uploading a photo from my device to Google Photos
I've just restarted my phone
I've just awakened my phone from sleep
My phone turns on after having been turned off with the Google App in the foreground (i.e. when the Google App is on the screen when the phone turns on)

Not actually a duplicate This question may appear to have been asked before, but those questions are about when the toast shows up in the Play Store app; I have nonetheless followed answers' instructions from those questions (instructions like clearing Play Store cache), but to no avail.
These toasts are annoying and I'd like to determine the source. Could it be an app? The Play Store? Google Photos? Or a system prompt?
What I've tried so far

Restarting phone
Switching WiFi networks, switching to Cellular
Clearing Play Store cache
Toggling Hotspot/Tethering on/off
Toggling Airplane Mode on/off

Phone Specs
Nexus 6P, Android 6.0.1, not rooted, has Project Fi as carrier (used to be on AT&amp;T, issue occurred then too)
Edit: One other solution to a similar question mentions the Freedom app, but I don't have that installed.
Based on your assertion that your issue is not Play Store-related, I believe it is a malfunctioning app.

The Toaster app will help you track down the source of these "toast " notifications.

The app description reads:


  Records every toast message including the sender package. May be helpful if you get messages and don't know which app sends it.


Update: As confirmed by OP, the Toaster app worked and the app responsible for the repeated notifications (as determined by Toaster) is NYTVR, the VR app of New York Times. Interestingly, there is one  user review there which complains of the same problem faced by you!

Update 2: I tried downloading the NYTVR app to see if the same problem would arise (I am also on same OS, though I have a Moto X Play); however, I did not encounter any such notifications, which makes me think that this may not be purely OS-related, but rather a general bug in the NYTVR app that only occurs on certain devices. 



If Toaster indicates that a certain app is sending the notification, make sure that app is updated and has settings set in a standard way. If you can't stop the notifications, contact the developer of the app or uninstall it.

Hope this helps!