Same issues here. ZTE Axon 7 running 7.1.1 with "waiting for network" message when attempting to download anything from the Google Play Store.
Only fix thus far is to "Uninstall Updates" from the Google Play Store application. Be careful to cancel the automatic update of Google Play Store app the next time you open it, or you'll have to repeat the process.
I have found that doing this seems to bugger my Android Auto, and basically removes links to any 3rd party apps (Like Slacker or Pocket Casts) and requires an uninstall & reinstall of those apps for Android Auto to "re-link" them into the app. This seems to be a Google Play Store issue, not an issue that is specific to one particular manufacturer.