Well, apparently, the problem is solved, at least for me. Thanks!
First I reinstalled the packages Laserman mentioned. The problem persisted, but then I found out that Rhythmbox was not recognizing the bitrate of most of my mp3 files. The ones whose bitrate was recognized were "skippable". So I rebuilt my music library and now everything is working just fine.