[SOLVED]: rhythmbox does not play mp3 file

Yes, it should play and you have already double checked  that gstreamer was installed with all possible plugins. Also was installed apt://ubuntu-restricted-extras on Ubuntu or ugly on fedora

# yum install gstreamer gstreamer-ffmpeg gstreamer-plugins-bad gstreamer-plugins-bad-free gstreamer-plugins-bad-free-extras gstreamer-plugins bad-nonfree gstreamer-plugins-base gstreamer-plugins-good gstreamer-plugins-ugly install faad2 faac libdca wget compat-libstdc++-33 compat-libstdc++-296  xine-lib-extras-freeworld

just execute following command, which helped me a lot

# cd ~/Music
# find . -exec touch '{}' \;

Enjoy with mp3 on rhythmbox!