I was having a similar issue with Clementine on this thread:
The issue ended up being resolved with a simple update provided by the software updater. Make sure your system is up to date and also check the codecs in the welcome menu if you haven't done that already.