I'm on Fedora 19 which has rhythmbox 2.99.1 and gtk3 3.8.2, but I'm also seeing this with rhythmbox git as of today.

To reproduce: start with a fresh rhythmbox config, and just start adding playlists. When you get to 10-15 things will slow down a lot. Select a playlist and up/down arrow between them, for me it takes over a second to switch. To reiterate there is nothing in the library or any of the playlists.

Also, after triggering the slowness, shutting down the app then takes upwards of 10 seconds: the main window closes but the app doesn't go away. debug output shows it taking a long time cleaning up each playlist source.

In rb_shell_clipboard_set_source_internal, commenting out the last two lines (the calls to add_delete_menu_item and setup_add_to_playlist_menu) makes the above 2 issues go away. I poked down a bit further and it seems related to g_menu linking and rb_application_add_shared_menu  but I don't understand that stuff at all so I'll let you guys take a look.

(Also I can't get any right click menus to work for playlists or ipod, which may be related. Nothing pops up at all.)

Let me know if there's any more info to provide, I'm happy to help figure this issue out.