So I've carefully checked all those similar questions posted, tried their solutions.
Just in case that I've missed anything, here are the packages info for gstreamer installation:
Also ubuntu-restricted-extras was installed.
I'm pretty sure the files are not corrupted since VLC media player plays without a problem, also I used rhythmbox to play them like one week ago, perfectly fine. The error just occurred this time.
Music players I've tried: rhythmbox, banshee, clementine, and all throwing me the same error message.
Any help I can get from here?
p.s I'm using ubuntu 16.04 LTS system, with a windows 10 dual boot