I had problems with AppStore downloads, iOS updates, Apple Watch updates, and some banking apps (on initial setup), even Plants vs. Zombies Heroes after I updated to iOS10, on two different phones. No problem with other apps, and no problems with my iPad mini 2. Then recently I found out the problem was some custom DNS settings on the phone, or a WiFi network that has a "Security recommendation" when you go into the WiFi settings. I reset the DNS settings (empty the field out and go back, it will re-populate with the default), and fixed the security recommendation (for my case it was a hidden SSID). Did both and now no problems anymore, no matter how hard I try.