I cannot confirm this with the fifth generation iPod, however, I don't believe it is Shuffle specific. Which version of Rhythmbox do you have? -- adding songs to ipod shuffle doesn't update iTunesDB properly https://launchpad.net/bugs/68300