How can I block Spotify on our company network?

You can fix this sort of thing via technology - basically firewall off the sources and/or ports - but I'm a big believer in not turning a HR problem into a game of cat'n'mouse with your users.

Simply speak to HR, explain the problem and ask them to make a policy regarding this issue and have them communicate it to your users. Then simply agree with HR to do periodic traffic analysis, letting them know of any users breaking this policy and have them deal with the them.

Basically trying to fix it yourself will just get you tied up in knots, and utterly hated too, which as we know is the job of HR already :)

You can install spotify yourself, sniff the traffic, and block outbound connections to their servers on your firewall.

Or

You can get a rate shaper that does packet inspection and shape the traffic for streaming audio to zero or close to it, then whitelist any legitimate audio streaming sites that you approve.