We’ve found the root of the issue, and unfortunately it won’t be so simple as updating our Spotify client yet again.
Spotify has made some sort of change that makes Spotify Connect either not work or work fairly poorly on a per-account basis, basically some people are unaffected and others are affected to varying degrees with symptoms including losing metadata, losing connection on song change, or outright never being able to connect in the first place.
Here’s a post on the Spotify Community Forum that helped us find the nature of this issue, if you’d like a citation