diff -ur ../rhythmbox-svn/plugins/daap/rb-daap-source.c ./plugins/daap/rb-daap-source.c
--- ../rhythmbox-svn/plugins/daap/rb-daap-source.c	2008-01-04 22:57:10.000000000 +0000
+++ ./plugins/daap/rb-daap-source.c	2008-01-13 23:21:12.000000000 +0000
@@ -535,7 +535,12 @@
 		RBDAAPPlaylist *playlist = l->data;
 		RBSource *playlist_source;
 
-		playlist_source = rb_static_playlist_source_new (shell, playlist->name, FALSE, entry_type);
+		/* Construct a unique sorting name for this playlist, as <Share Name>_<Playlist> */
+		gchar *sorting_name = g_strjoin(NULL, daap_source->priv->service_name, "_", playlist->name, NULL);
+
+		playlist_source = rb_static_playlist_source_new (shell, playlist->name, sorting_name, FALSE, entry_type);
+		g_free (sorting_name);
+
 		g_list_foreach (playlist->uris, (GFunc)_add_location_to_playlist, playlist_source);
 
 		rb_shell_append_source (shell, playlist_source, RB_SOURCE (daap_source));
diff -ur ../rhythmbox-svn/plugins/ipod/rb-ipod-source.c ./plugins/ipod/rb-ipod-source.c
--- ../rhythmbox-svn/plugins/ipod/rb-ipod-source.c	2008-01-04 22:57:10.000000000 +0000
+++ ./plugins/ipod/rb-ipod-source.c	2008-01-13 23:21:12.000000000 +0000
@@ -371,6 +371,7 @@
 
 	playlist_source = rb_static_playlist_source_new (shell,
 							 playlist->name,
+							 NULL,
 							 FALSE,
 							 entry_type);
 	g_boxed_free (RHYTHMDB_TYPE_ENTRY_TYPE, entry_type);
diff -ur ../rhythmbox-svn/shell/rb-playlist-manager.c ./shell/rb-playlist-manager.c
--- ../rhythmbox-svn/shell/rb-playlist-manager.c	2008-01-04 22:57:09.000000000 +0000
+++ ./shell/rb-playlist-manager.c	2008-01-13 23:21:12.000000000 +0000
@@ -937,6 +937,7 @@
 	else
 		playlist = rb_static_playlist_source_new (mgr->priv->shell,
 							  suggested_name,
+							  NULL,
 							  TRUE,
 							  RHYTHMDB_ENTRY_TYPE_SONG);
 
diff -ur ../rhythmbox-svn/sources/rb-playlist-source.c ./sources/rb-playlist-source.c
--- ../rhythmbox-svn/sources/rb-playlist-source.c	2007-12-19 21:16:58.000000000 +0000
+++ ./sources/rb-playlist-source.c	2008-01-13 23:38:43.000000000 +0000
@@ -93,7 +93,11 @@
 						     GtkTreeModel *tree_model, GtkTreeIter *iter,
 						     RBPlaylistSource *source);
 static void default_mark_dirty (RBPlaylistSource *source);
+static void rb_playlist_source_songs_sort_order_changed_cb (RBEntryView *view,
+						RBStaticPlaylistSource *source);
+static gchar *rb_playlist_make_sorting_key (RBPlaylistSource *source);
 
+#define CONF_STATE_SORTING_PREFIX CONF_PREFIX "/state/sorting/"
 #define PLAYLIST_SOURCE_SONGS_POPUP_PATH "/PlaylistViewPopup"
 #define PLAYLIST_SOURCE_POPUP_PATH "/PlaylistSourcePopup"
 
@@ -112,6 +116,7 @@
 	gboolean dispose_has_run;
 
 	char *title;
+	char *sorting_name;
 };
 
 #define RB_PLAYLIST_SOURCE_GET_PRIVATE(o) (G_TYPE_INSTANCE_GET_PRIVATE ((o), RB_TYPE_PLAYLIST_SOURCE, RBPlaylistSourcePrivate))
@@ -122,6 +127,7 @@
 	PROP_DB,
 	PROP_DIRTY,
 	PROP_LOCAL,
+	PROP_SORTING_NAME
 };
 
 static const GtkTargetEntry target_uri [] = { { "text/uri-list", 0, 0 } };
@@ -178,6 +184,13 @@
 							       "whether this playlist is attached to the local library",
 							       TRUE,
 							       G_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
+	g_object_class_install_property (object_class,
+					 PROP_SORTING_NAME,
+					 g_param_spec_string ("sorting-name",
+					 		      "sorting-name",
+				"globally unique name for storing sort-order",
+					 		      NULL,
+					 				 G_PARAM_READWRITE));
 
 	g_type_class_add_private (klass, sizeof (RBPlaylistSourcePrivate));
 }
@@ -222,6 +235,7 @@
 	RBShell *shell;
 	RhythmDB *db;
 	RhythmDBQueryModel *query_model;
+	gchar *sorting_key;
 
 	klass = RB_PLAYLIST_SOURCE_CLASS (g_type_class_peek (RB_TYPE_PLAYLIST_SOURCE));
 
@@ -238,9 +252,18 @@
 	source->priv->entries = g_hash_table_new_full (rb_refstring_hash, rb_refstring_equal,
 						       (GDestroyNotify)rb_refstring_unref, NULL);
 
+	/* If a sorting key is available at construction time, use it. This may be
+	 * NULL in which case a key may be assigned later through a set property. */
+	sorting_key = rb_playlist_make_sorting_key (source);
 	source->priv->songs = rb_entry_view_new (source->priv->db,
 						 shell_player,
-					 	 NULL, TRUE, TRUE);
+					 	 sorting_key, TRUE, TRUE);
+	g_free (sorting_key);
+
+	g_signal_connect_object (source->priv->songs,
+					 "sort-order-changed",
+					 G_CALLBACK (rb_playlist_source_songs_sort_order_changed_cb),
+					 source, 0);
 
 	query_model = rhythmdb_query_model_new_empty (source->priv->db);
 	rb_playlist_source_set_query_model (source, query_model);
@@ -360,6 +383,15 @@
 	case PROP_LOCAL:
 		source->priv->is_local = g_value_get_boolean (value);
 		break;
+	case PROP_SORTING_NAME:
+		g_free (source->priv->sorting_name);
+		source->priv->sorting_name = g_value_dup_string (value);
+
+		/* propagate sorting key to the entry view */
+		gchar *sorting_key = rb_playlist_make_sorting_key (source);
+		g_object_set (source->priv->songs, "sort-key", sorting_key, NULL);
+		g_free (sorting_key);
+		break;
 	default:
 		G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
 		break;
@@ -384,6 +416,9 @@
 	case PROP_LOCAL:
 		g_value_set_boolean (value, source->priv->is_local);
 		break;
+	case PROP_SORTING_NAME:
+		g_value_set_string (value, source->priv->sorting_name);
+		break;
 	default:
 		G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
 		break;
@@ -868,3 +903,36 @@
 	return TRUE;
 }
 
+static void
+rb_playlist_source_songs_sort_order_changed_cb (RBEntryView *view,
+						RBStaticPlaylistSource *source)
+{
+	rb_debug ("sort order changed");
+	rb_entry_view_resort_model (view);
+}
+
+/* takes the 'sorting-name' property and produces a full GConf key for storing
+ * the playlist's column sort order */
+gchar *
+rb_playlist_make_sorting_key (RBPlaylistSource *source)
+{
+	gchar *sorting_name, *sorting_key, *sorting_key_tail;
+	g_object_get (source, "sorting-name", &sorting_name, NULL);
+
+	if(sorting_name && sorting_name[0] != '\0') {
+		/* escape invalid characters in the key name */
+		sorting_key_tail = gconf_escape_key (sorting_name, -1);
+
+		/* bind column sort order to a full gconf key */
+		sorting_key = g_strjoin(NULL, CONF_STATE_SORTING_PREFIX, 
+					sorting_key_tail, NULL);
+
+		g_free (sorting_key_tail);
+	} else {
+		sorting_key = NULL;
+	}
+	g_free (sorting_name);
+
+	return sorting_key;
+}
+
diff -ur ../rhythmbox-svn/sources/rb-static-playlist-source.c ./sources/rb-static-playlist-source.c
--- ../rhythmbox-svn/sources/rb-static-playlist-source.c	2008-01-04 22:57:09.000000000 +0000
+++ ./sources/rb-static-playlist-source.c	2008-01-13 23:21:12.000000000 +0000
@@ -297,13 +297,17 @@
 }
 
 RBSource *
-rb_static_playlist_source_new (RBShell *shell, const char *name, gboolean local, RhythmDBEntryType entry_type)
+rb_static_playlist_source_new (RBShell *shell, const char *name, const char *sorting_name, gboolean local, RhythmDBEntryType entry_type)
 {
 	if (name == NULL)
 		name = "";
 
+	if (sorting_name == NULL)
+		sorting_name = "";
+
 	return RB_SOURCE (g_object_new (RB_TYPE_STATIC_PLAYLIST_SOURCE,
 					"name", name,
+					"sorting-name", sorting_name,
 					"shell", shell,
 					"is-local", local,
 					"entry-type", entry_type,
@@ -337,6 +341,7 @@
 {
 	RBSource *psource = rb_static_playlist_source_new (shell,
 							   NULL,
+							   NULL,
 							   TRUE,
 							   RHYTHMDB_ENTRY_TYPE_SONG);
 	RBStaticPlaylistSource *source = RB_STATIC_PLAYLIST_SOURCE (psource);
diff -ur ../rhythmbox-svn/sources/rb-static-playlist-source.h ./sources/rb-static-playlist-source.h
--- ../rhythmbox-svn/sources/rb-static-playlist-source.h	2008-01-04 22:57:09.000000000 +0000
+++ ./sources/rb-static-playlist-source.h	2008-01-13 23:21:12.000000000 +0000
@@ -51,6 +51,7 @@
 
 RBSource *	rb_static_playlist_source_new		(RBShell *shell,
 							 const char *name,
+							 const char *sorting_name,
 							 gboolean local,
 							 RhythmDBEntryType entry_type);
 
diff -ur ../rhythmbox-svn/widgets/rb-entry-view.c ./widgets/rb-entry-view.c
--- ../rhythmbox-svn/widgets/rb-entry-view.c	2008-01-13 23:20:42.000000000 +0000
+++ ./widgets/rb-entry-view.c	2008-01-13 23:21:12.000000000 +0000
@@ -265,7 +265,7 @@
 							      "sorting key",
 							      "sorting key",
 							      "",
-							      G_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
+							      G_PARAM_READWRITE));
 	g_object_class_install_property (object_class,
 					 PROP_IS_DRAG_SOURCE,
 					 g_param_spec_boolean ("is-drag-source",
@@ -573,6 +573,7 @@
 			    const GValue *value,
 			    GParamSpec *pspec)
 {
+	gchar *old_sorting_key;
 	RBEntryView *view = RB_ENTRY_VIEW (object);
 
 	switch (prop_id) {
@@ -583,8 +584,39 @@
 		rb_entry_view_set_shell_player_internal (view, g_value_get_object (value));
 		break;
 	case PROP_SORTING_KEY:
-		g_free (view->priv->sorting_key);
+		/* Remove notification on old key, if any. */
+		if (view->priv->sorting_key) {
+			eel_gconf_notification_remove (view->priv->sorting_gconf_notification_id);
+			view->priv->sorting_gconf_notification_id = 0;
+		}
+
+		old_sorting_key = view->priv->sorting_key;
 		view->priv->sorting_key = g_value_dup_string (value);
+
+		if (view->priv->sorting_key && view->priv->sorting_key[0] != '\0') {
+			/* Set up notification on the new key. */
+			view->priv->sorting_gconf_notification_id =
+						 eel_gconf_notification_add (view->priv->sorting_key,
+						 rb_entry_view_sort_key_changed_cb, view);
+
+			rb_entry_view_set_columns_clickable (view, TRUE);
+
+			/* If there was already a sorting key, assume this is a rename. */
+			if (old_sorting_key && old_sorting_key[0] != '\0') {
+				/* Propagate existing sort order into the new GConf key. */
+				eel_gconf_set_string (view->priv->sorting_key,
+							 rb_entry_view_get_sorting_type(view));
+
+				eel_gconf_unset (old_sorting_key);
+			}
+
+			/* Synchronise UI sorting order with the new key. */
+			gchar *new_sorting_type = eel_gconf_get_string (view->priv->sorting_key);
+			rb_entry_view_set_sorting_type (view, new_sorting_type);
+			g_free (new_sorting_type);
+		}
+
+		g_free (old_sorting_key);
 		break;
 	case PROP_MODEL:
 		rb_entry_view_set_model_internal (view, g_value_get_object (value));
@@ -1475,18 +1507,6 @@
 		eel_gconf_notification_add (CONF_UI_COLUMNS_SETUP,
 					    rb_entry_view_columns_config_changed_cb,
 					    view);
-	if (view->priv->sorting_key) {
-		view->priv->sorting_gconf_notification_id =
-			eel_gconf_notification_add (view->priv->sorting_key,
-						    rb_entry_view_sort_key_changed_cb,
-						    view);
-	}
-
-	if (view->priv->sorting_key) {
-		char *s = eel_gconf_get_string (view->priv->sorting_key);
-		rb_entry_view_set_sorting_type (view, s);
-		g_free (s);
-	}
 
 	{
 		RhythmDBQueryModel *query_model;
