Since reinstalling the codecs, have you deleted the contents of ~/.local/share/rhythmbox ?
(particularly rhythmdb.xml and playlists.xml, although rhythmdb.xml is probably the main culprit)
I kept having the problem, so I
...reloaded all plugins,
...yum updated everything,
...even loaded both x64 and i686 versions of plugins just to be sure
THEN just figured like with other stuff maybe it just needs to be reset...
...renamed the offending files (a-la-mv)
...ran rhythmbox, comes up clean and empty.
...turned "watch..." back on in preferences
and everything loaded into the library with zero notifications.
I have been able to replicate this solution on additional fedora 13 x64 workstations.
Hope this helps. I was inspired by this thread to keep digging, just wanted to pass it on.