I have been receiving pretty good service from Spotify, but recently noticed the app freezes when I am scrolling through the playlist every so often. If I wait about 15 seconds, it unfreezes and allows me to proceed. Once in while I get an error message and have to close and reopen the app. Not that big a deal, but something I have not noticed before. I have an epic 4g galaxy 1 on Sprint. I use 3g exclusively on the mobile.
It sounds like the cache has got a little cluttered. You might want to pop over to the settings menu and clear it out. However, this does also mean that any offline playlists you have will need to be resynced.