The only time I've experienced anything like this is when I've turned wifi on and then jumped right into the Play Store as it's connecting. Even then, if I back out and go back in, it loads up and downloads just fine. I always toggle wifi off when I leave the house, because I don't want to be jumping onto unsecured networks that I don't know/trust personally, and sometimes I get ahead of myself when I first get home and turn it back on.
Anyway, I wouldn't be surprised if the issue is what cr6 describes. I know there's a hospital in my area that blocks sites like xboxlive.com and others on their public wifi. It's strange what and why some places block what they do, but it's a pretty safe bet that they'd block things that are going to use up extra bandwidth.
I'm not really sure how blocking just the Play Store would work on an access point, but I suppose there's got to be an underlying domain/IP that your device connects to to access it. If that's the case, successfully downloading an app using the Amazon App store wouldn't mean that they're not blocking you from downloading apps. It would just mean that they haven't blocked that on their end. So, basically, it's not that simple to narrow down what's going on without knowing the setup of the network(s) in question.
However, like Sajokaz said, if it's always happening at those locations, safe bet is that they've blocked it. If it's not consistently blocking, there's a good chance that there's some hiccup in your Play Store app or something. I realize that's a lot of rambling that doesn't really answer your question, but just thought I'd throw a bit more info out there.
One thing you could try would be to download a VPN app and connect through that. That spoofs your IP to make it appear that you're connecting to the internet from elsewhere. It also protects you from would-be hackers, because they won't see you on that open network since you're technically connected to the 'net through a Virtual Private Network. This is a good idea on an unsecured wifi connection no matter what to keep your data more secure. The same trick has been used by some to trick Netflix into believing they're in another country, allowing them to view content that isn't supposed to be available in their region.
If you can download using a VPN, I'd say they're definitely blocking downloads.
