For example, the default MP3's included with Windows Media player play fine in Windows Media Player.
When I play those same tracks via Spotify's Local Collection, I hear the crackle/pops and stutter randomly, just like Spotify native tracks. That led me to believe it's an issue with the Application itself.
For me this is now happening not only with Spotify but with any streaming content (YouTube, etc). It doesn not happen with local saved files. This makes me think the problem is with my sound card chip or driver, but I haven't been able to find a fix. All drivers are up to date. I'm using a new Dell Latitude e6250. NVIDIA High Definition Audio + IDT High Definition Audio Codec.
If it only happens with local files: do you have those on your harddisk or an external or network drive? If it mainly occurs with all streaming and not local files: maybe you have some network issues. Try rebooting your router.
Slightly different behavious today - seems to be crackling less, but it's still there. I've tried both in offline mode and while online, with a playlist that's downloaded, and the crackles are there in both cases. Notably it crackels when you pause and unpause.
I then undownloaded the playlist, and played it again - still the same.
There is an easy solution for your problem! It seems that the virus scanners are screening your stream continuously. I excluded the spotify.exe process and everything works fine right now. I use Microsoft security essentials & Malwarebytes. For Malwarebytes I took the whole map in user/appdata/roaming/Spotify!
I also have that problem on my Nexus 7 and Nexus S but it only happens when I play and pause the music. Afterwards I'm not hearing it at all. I'm trying to live with it, I'm using Google Music for playing my cd's. Shame Spotify won't improve their services because it has a lot potential. They should be giving us and the musicians a platform like the new Myspace :)
I think the amount of troubleshooting going on in this thread is pointing to a non-environment issue. It seems to be a software issue. Given the fact that for me it happens not just on Spotify tracks, but also playing non-Spotify local files THROUGH the Spotify software, it's got to be a software issue.
I had my work laptop re-imaged for another issue, and a fresh install of Spotify on a fresh install of Windows still didn't solve the problem.