Okay, I figured out the root of the problem: it' avahi. I removed avahi, and rhythmbox now works smoothly even when I'm not connected to the internet. I guess avahi needed to timeout or something before the song could be changed. This might also be because of a configuration issue in the default feisty avahi.
-- [feisty] rhythmbox hangs between songs when not connected to the internet https://launchpad.net/bugs/96153 -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs
