What can change so the app store fails on a network where purchases used to work fine?
You should be able to filter your firewall logs down to requests originating from your computer/your phone's local IP address, and look it it's outgoing requests.

I'm pretty sure all that app download traffic takes place over bog standard HTTPS, 443/tcp. 

Ensure all apps have stopped running, open App Store, move over to the Updates category, wait for all traffic (app image requests and the like) to die down, then tap update. The next series of requests should fail, and you should have the reason relevant to your own configuration.