are you using the latest version of rekordbox? Cause in the latest release there's a new feature called "Synchronization" where you can ensure all the playlists and folders of playlists are always updated whenever your device is connected.
In my case I have a "Summer 2013" Folder and have playlists within that folder that are automatically updated on my external HDD-