That bug has been opened on https://launchpad.net/ubuntu/+source/rhythmbox/+bug/84014

"When rhythmbox starts to play new file in random play mode, rhythmbox stops randomly playing until I move the slider some seconds forward from 0:00.
After that playing works.

ProblemType: Bug
Date: Thu Feb 8 18:05:43 2007
DistroRelease: Ubuntu 7.04
Uname: Linux unelma-laptop 2.6.20-6-generic #2 SMP Wed Jan 31 20:53:39 UTC 2007 i686 GNU/Linux
...
http://librarian.launchpad.net/6349456/strace-rhythmbox.log.tar.gz
strace

strace -Ff -tt -p 6467 2>&1 | tee strace-rhythmbox.log
...
> Thank you for your bug. Could you run "rhyhtmbox -d" from a command line and note to a comment what happens when it hangs or attach the log to the bug?
...
http://librarian.launchpad.net/6387935/rhythmbox.log
Tail of output of rhythmbox -d

I have a similar problem with Rhythmbox 0.9.7 in Feisty, but it occurs also in normal (linear) playback mode, and only with one particular Ogg Vorbis file (as far as I am aware). When either selected for playback manually, or automatically after the end of the previous track, the selected track will not start playing, it will just stick at 0:00. As reported above, seeking forward will start playback from the appropriate point.

I've verified that this does not occur in Edgy (0.9.6-0ubuntu4) with the same file.

Output of rhythmbox -d attached.
..."