Spotify skips all the songs right away on Ubuntu 16.04

[Mehran20]

I've just installed a fresh new Ubuntu 16.04 and then Spotify client. But when I choose some category or channel, nothing plays and all the songs start skipping so fast. I've tried a couple of solutions here and there but so far nothing helps.

It is worth mentioning that I can play the Spotify web player and only the desktop version is facing the problem. When I run the Spotify from command prompt, this is what I see:

$ spotify 
Gtk-Message: Failed to load module "overlay-scrollbar"
Gtk-Message: Failed to load module "gail"
Gtk-Message: Failed to load module "atk-bridge"
Gtk-Message: Failed to load module "canberra-gtk-module"
shm_open() failed: Permission denied
shm_open() failed: Permission denied

But even though, the app starts and everything seems fine but nothing plays and songs just keep skipping. Any idea what's wrong?