App works when it wants.

[Eksistenze]

Everyone I use the app, it is very slow. Search is slow, if it works at all. Sometimes it tells me I am offline when I'm not. Sometimes the search will just time out. When I try loading my artists/albums/tracks, it will only load maybe half and the rest are all #. However, I can control the phone just fine from my computer. This happens on Wi-Fi and 4g.

I have done a phone reset and clean install. I'm on a HTC One M8
Android 5.0.1
Spotify 2.9.0.890