tl;dr: Spotify Connect doesn't work with iptables, please use fixed instead of random ports for mDNS and SSDP to facilitate a more secure firewall configuration.
So I discovered that after enabling UFW (a iptables front-end), Spotify Connect stopped working with my AVR. After examining the UFW logs and some wireshark dumps I discovered that Spotify uses mDNS and SSDP to look for Spotify Connect devices without login on the local network (devices such as phones on which you're logged in still get detected via Spotify's servers). Problem with this (and iptables) is that since mDNS och SSDP uses multicast to send out queries, conntrack (the connection tracking module) doesn't regard it as a connection and doesn't track it, thus resulting in the responses getting dropped.
This is not a problem with Spotify per say, but rather a problem with the nature of mDNS/SSDP and conntrack. However, to work around this I suggest that developers use fixed ports for mDNS/SSDP request to facilitate creating firewall rules that aren't overly broad and unsecure, since the only option right now is to create a rule that accept all UDP traffic coming from port 1900 and 5353 on your local network, such as this:
sudo ufw allow proto udp from 192.168.0.0/24 port 1900,5353 to any port 1025:65535
which may open up for attacks on services listening on any of those ports.