diff --git a/rhythmdb/rhythmdb-tree.c b/rhythmdb/rhythmdb-tree.c
index 1a86faf..b717b5b 100644
--- a/rhythmdb/rhythmdb-tree.c
+++ b/rhythmdb/rhythmdb-tree.c
@@ -1082,9 +1082,16 @@ save_entry (RhythmDBTree *db,
 
 			for (l = keywords; l != NULL; l = g_list_next (l)) {
 				RBRefString *keyword = (RBRefString*)l->data;
+				const char *keyword_str = rb_refstring_get (keyword);
+				// We will skip the playlist keywords -- those should be read
+				// in each time the program starts, so that they don't get out
+				// of sync.
+				if (strstr(keyword_str, "rb:in-playlist:") == keyword_str) {
+					continue;
+				}
 
 				RHYTHMDB_FWRITE_STATICSTR ("    <keyword>", ctx->handle, ctx->error);
-				encoded	= xmlEncodeEntitiesReentrant (NULL, BAD_CAST rb_refstring_get (keyword));
+				encoded	= xmlEncodeEntitiesReentrant (NULL, BAD_CAST keyword_str);
 				RHYTHMDB_FWRITE (encoded, 1, xmlStrlen (encoded), ctx->handle, ctx->error);
 				g_free (encoded);
 				RHYTHMDB_FWRITE_STATICSTR ("</keyword>\n", ctx->handle, ctx->error);
diff --git a/sources/rb-auto-playlist-source.c b/sources/rb-auto-playlist-source.c
index 834a62c..d77a8b6 100644
--- a/sources/rb-auto-playlist-source.c
+++ b/sources/rb-auto-playlist-source.c
@@ -375,7 +375,7 @@ rb_auto_playlist_source_get_property (GObject *object,
  * Return value: the new source
  */
 RBSource *
-rb_auto_playlist_source_new_from_xml (RBShell *shell, xmlNodePtr node)
+rb_auto_playlist_source_new_from_xml (RBShell *shell, xmlNodePtr node, xmlChar *name)
 {
 	RBAutoPlaylistSource *source = RB_AUTO_PLAYLIST_SOURCE (rb_auto_playlist_source_new (shell, NULL, TRUE));
 	xmlNodePtr child;
@@ -387,6 +387,11 @@ rb_auto_playlist_source_new_from_xml (RBShell *shell, xmlNodePtr node)
 	gint sort_direction = 0;
 	GValue val = {0,};
 
+	// Make sure the name is set appropriately.
+	if (source != NULL) {
+		g_object_set (G_OBJECT (source), "name", name, NULL);
+	}
+
 	child = node->children;
 	while (xmlNodeIsText (child))
 		child = child->next;
diff --git a/sources/rb-auto-playlist-source.h b/sources/rb-auto-playlist-source.h
index 9ebda29..cface4c 100644
--- a/sources/rb-auto-playlist-source.h
+++ b/sources/rb-auto-playlist-source.h
@@ -64,7 +64,8 @@ RBSource *	rb_auto_playlist_source_new		(RBShell *shell,
 							 gboolean local);
 
 RBSource *	rb_auto_playlist_source_new_from_xml	(RBShell *shell,
-							 xmlNodePtr node);
+							 xmlNodePtr node,
+							 xmlChar *name);
 
 void		rb_auto_playlist_source_set_query	(RBAutoPlaylistSource *source,
 							 GPtrArray *query,
diff --git a/sources/rb-playlist-source.c b/sources/rb-playlist-source.c
index 44e8ed1..e5ff2ef 100644
--- a/sources/rb-playlist-source.c
+++ b/sources/rb-playlist-source.c
@@ -743,23 +743,19 @@ rb_playlist_source_new_from_xml	(RBShell *shell,
 	tmp = xmlGetProp (node, RB_PLAYLIST_TYPE);
 
 	if (!xmlStrcmp (tmp, RB_PLAYLIST_AUTOMATIC))
-		source = rb_auto_playlist_source_new_from_xml (shell, node);
+		source = rb_auto_playlist_source_new_from_xml (shell, node, name);
 	else if (!xmlStrcmp (tmp, RB_PLAYLIST_STATIC))
-		source = rb_static_playlist_source_new_from_xml (shell, node);
+		source = rb_static_playlist_source_new_from_xml (shell, node, name);
 	else if (!xmlStrcmp (tmp, RB_PLAYLIST_QUEUE)) {
 		RBStaticPlaylistSource *queue;
 
 		g_object_get (shell, "queue-source", &queue, NULL);
-		rb_static_playlist_source_load_from_xml (queue, node);
+		rb_static_playlist_source_load_from_xml (queue, node, name);
 		g_object_unref (queue);
 	} else {
 		g_warning ("attempting to load playlist '%s' of unknown type '%s'", name, tmp);
 	}
 
-	if (source != NULL) {
-		g_object_set (G_OBJECT (source), "name", name, NULL);
-	}
-
 	xmlFree (name);
 	xmlFree (tmp);
 
diff --git a/sources/rb-static-playlist-source.c b/sources/rb-static-playlist-source.c
index 4cd3977..0056fce 100644
--- a/sources/rb-static-playlist-source.c
+++ b/sources/rb-static-playlist-source.c
@@ -391,10 +391,15 @@ rb_static_playlist_source_get_property (GObject *object,
 }
 
 void
-rb_static_playlist_source_load_from_xml (RBStaticPlaylistSource *source, xmlNodePtr node)
+rb_static_playlist_source_load_from_xml (RBStaticPlaylistSource *source, xmlNodePtr node, xmlChar *name)
 {
 	xmlNodePtr child;
 
+	// Make sure that the name is set appropriately.
+	if (source != NULL) {
+		g_object_set (G_OBJECT (source), "name", name, NULL);
+	}
+
 	for (child = node->children; child; child = child->next) {
 		xmlChar *location;
 
@@ -412,7 +417,7 @@ rb_static_playlist_source_load_from_xml (RBStaticPlaylistSource *source, xmlNode
 }
 
 RBSource *
-rb_static_playlist_source_new_from_xml (RBShell *shell, xmlNodePtr node)
+rb_static_playlist_source_new_from_xml (RBShell *shell, xmlNodePtr node, xmlChar *name)
 {
 	RBSource *psource = rb_static_playlist_source_new (shell,
 							   NULL,
@@ -421,7 +426,7 @@ rb_static_playlist_source_new_from_xml (RBShell *shell, xmlNodePtr node)
 							   RHYTHMDB_ENTRY_TYPE_SONG);
 	RBStaticPlaylistSource *source = RB_STATIC_PLAYLIST_SOURCE (psource);
 
-	rb_static_playlist_source_load_from_xml (source, node);
+	rb_static_playlist_source_load_from_xml (source, node, name);
 
 	return RB_SOURCE (source);
 }
@@ -707,6 +712,9 @@ rb_static_playlist_source_add_location_internal (RBStaticPlaylistSource *source,
 {
 	RhythmDB *db;
 	RhythmDBEntry *entry;
+	RBRefString *playlist_keyword;
+	char *name;
+	char *keyword;
 	RBPlaylistSource *psource = RB_PLAYLIST_SOURCE (source);
 	if (rb_playlist_source_location_in_map (psource, location))
 		return;
@@ -725,6 +733,22 @@ rb_static_playlist_source_add_location_internal (RBStaticPlaylistSource *source,
 
 	rb_playlist_source_add_to_map (psource, location);
 
+	// The keyword should be:
+	// "rb:in-playlist:<playlist-id>"
+	g_object_get(source, "name", &name, NULL);
+	keyword = g_malloc((strlen("rb:in-playlist:") + strlen(name) + 1) * sizeof(char));
+	sprintf(keyword, "rb:in-playlist:%s", name);
+	playlist_keyword = rb_refstring_new (keyword);
+	rb_refstring_ref (playlist_keyword);
+	g_free(keyword);
+
+	// It'll return false if the keyword wasn't already on the entry.
+	// We don't have any use for that info here.
+	rhythmdb_entry_keyword_add (db,
+					 entry,
+					 playlist_keyword);
+	rb_refstring_unref (playlist_keyword);
+
 	rb_playlist_source_mark_dirty (psource);
 }
 
@@ -753,7 +777,7 @@ rb_static_playlist_source_add_location (RBStaticPlaylistSource *source,
 
 	db = rb_playlist_source_get_db (RB_PLAYLIST_SOURCE (source));
 	entry = rhythmdb_entry_lookup_by_location (db, location);
-
+	
 	/* if there is an entry, it won't be a directory */
 	if (entry == NULL && rb_uri_is_directory (location))
 		rb_uri_handle_recursively (location,
@@ -791,7 +815,29 @@ rb_static_playlist_source_remove_location (RBStaticPlaylistSource *source,
 	entry = rhythmdb_entry_lookup_by_location (db, location);
 
 	if (entry != NULL) {
-		RhythmDBQueryModel *model = rb_playlist_source_get_query_model (psource);
+		RhythmDBQueryModel *model;
+		char *name;
+		char *keyword;
+		RBRefString *playlist_keyword;
+
+		// We should remove this playlist's keyword from the entry.
+		// The keyword should be:
+		// "rb:in-playlist:<playlist-id>"
+		g_object_get(source, "name", &name, NULL);
+		keyword = g_malloc((strlen("rb:in-playlist:") + strlen(name)) * sizeof(char));
+		sprintf(keyword, "rb:in-playlist:%s", name);
+		playlist_keyword = rb_refstring_new (keyword);
+		rb_refstring_ref (playlist_keyword);
+		g_free(keyword);
+
+		// It'll return true if the keyword was already on the entry.  We
+		// don't have any use for that info here.
+		rhythmdb_entry_keyword_remove (db,
+						 entry,
+						 playlist_keyword);
+		rb_refstring_unref (playlist_keyword);
+
+		model = rb_playlist_source_get_query_model (psource);
 
 		/* if this fails, the model and the playlist are out of sync */
 		g_assert (rhythmdb_query_model_remove_entry (model, entry));
diff --git a/sources/rb-static-playlist-source.h b/sources/rb-static-playlist-source.h
index aa1f61a..06c0f02 100644
--- a/sources/rb-static-playlist-source.h
+++ b/sources/rb-static-playlist-source.h
@@ -64,9 +64,11 @@ RBSource *	rb_static_playlist_source_new		(RBShell *shell,
 							 RhythmDBEntryType entry_type);
 
 RBSource *	rb_static_playlist_source_new_from_xml	(RBShell *shell,
-							 xmlNodePtr node);
+							 xmlNodePtr node,
+							 xmlChar *name);
 void		rb_static_playlist_source_load_from_xml	(RBStaticPlaylistSource *source,
-							 xmlNodePtr node);
+							 xmlNodePtr node,
+							 xmlChar *name);
 
 void		rb_static_playlist_source_add_entry	(RBStaticPlaylistSource *source,
 						 	 RhythmDBEntry *entry,
