I still see this same problem on Ubuntu 16.04 using Rhythmbox 3.3:
$ dpkg -l rhythmbox |tail -1
ii rhythmbox 3.3-1ubuntu7 amd64music player and organizer for
GNOME
There is an upstream report about missing playlist sorting. Maybe it is
related, although a bit vague in its wording:
[Expired for rhythmbox (Ubuntu) because there has been no activity for
60 days.]
** Changed in: rhythmbox (Ubuntu)
Status: Incomplete => Expired
--
You received this bug notification because you are a member of Ubuntu
Bugs, which is subscribed to Ubuntu.
https://bugs.launchpad.net/bugs/10
Thank you for taking the time to report this bug and helping to make
Ubuntu better. We are sorry that we do not always have the capacity to
look at all reported bugs in a timely manner. There have been many
changes in Ubuntu since that time you reported the bug and your problem
may have been fixed
