Since your connection test was passing on the VPN connection that I had available, I decided to try it once again while connected to this VPN. This time it worked. I am not sure what I did differently compared to the last time - one thing that I did was connect to the VPN and start Steam only after that, that might have something to do with it.
Thanks for the help.