Downloader app failing to download apps over a specific wifi hotspot (Error 495)
Lucky for me, my router has a connection log, that I could look through.
From my phone that was trying to download an app, there were many connections, but these brought up my interest:

tcp   192.168.1.174:51959                      52.15.96.207:443                         SYN_SENT   
tcp   192.168.1.174:51974                      52.15.96.207:443                         SYN_SENT  


Indeed, the remote IP did not respond. But the feature worked on other access points. I decided to change the DNS settings in the DHCP server, from the ones provided by the ISP, to OpenDNS.

https://en.wikipedia.org/wiki/OpenDNS

This can also be done from the phone, from the advanced WiFi connection settings, when you choose something other than DHCP.

That did the trick.

As mentioned by What is error code 495 on Google Play and the YouTube app? too. Please, if this solves your problem, go upvote, so that it doesn't sit on the bottom of the answer list.