This bug was originally reported in the Debian BTS:
http://bugs.debian.org/229354

"> Let me summarize:
> 1- you do a search in your library

Yes, and start playing one of the songs that match the search.

> 2- you add some songs -> that add the files on the search result list

Yes, I add songs, some of which match the search pattern, and are therefore
displayed right and proper.

> 3- ?
> 
> I'm not sure of what to do after that. Play the first song of the list ? 
> If I play a song and click on the next button it jump to the next song
> on the list ... what's wrong ? What result are you expecting ?

Yep, here's where I appear to have missed a bit of information; the
next/previous buttons seem to work fine _if_ Shuffle is not on. If shuffle
is on, then the next/previous buttons ignore the newcomers. In fact, even
if one doesn't press anything but just waits for the songs to
change, the newly imported songs aren't played.

So this seems to actually a problem in the Shuffle functionality in
combination with importing new songs."