For me it also worked to just copy over my IP connection settings from "DHCP" settings to the "Static" tab in WiFi settings. So there is no need for a proxy server!
The problem seems to be, that creating new connections fails within the spotify app, which is most likely more easy with static IP settings. As long as the app has stable connections, everything is fine. My assumption is that this is also the reason, why unfortunately the search functionality does not work. Most probably the app tries to build a new connection for it?