diff --git a/backends/gstreamer/rb-player-gst-xfade.c b/backends/gstreamer/rb-player-gst-xfade.c
index 189e0af..a520f73 100644
--- a/backends/gstreamer/rb-player-gst-xfade.c
+++ b/backends/gstreamer/rb-player-gst-xfade.c
@@ -2221,6 +2221,7 @@ actually_start_stream (RBXFadeStream *stream, GError **error)
 		ret = link_and_unblock_stream (stream, error);
 	} else if (stream->crossfade == 0) {
 		GList *l;
+		GList *reap = NULL;
 		gboolean playing = FALSE;
 		for (l = player->priv->streams; l != NULL; l = l->next) {
 			RBXFadeStream *pstream = (RBXFadeStream *)l->data;
@@ -2236,12 +2237,22 @@ actually_start_stream (RBXFadeStream *stream, GError **error)
 				break;
 			case PAUSED:
 				rb_debug ("stream %s is paused; replacing it", pstream->uri);
-				unlink_and_dispose_stream (player, pstream);
+				/*unlink_and_dispose_stream (player, pstream);*/
+				reap = g_list_prepend (reap, g_object_ref (pstream));
 				break;
 			default:
 				break;
 			}
 		}
+		
+		/* drop the stream list lock to remove the streams, otherwise deadlock */
+		g_static_rec_mutex_unlock (&player->priv->stream_list_lock);
+		for (l = reap; l != NULL; l = l->next) {
+			RBXFadeStream *pstream = (RBXFadeStream *)l->data;
+			unlink_and_dispose_stream (player, pstream);
+			g_object_unref (pstream);
+		}
+		g_static_rec_mutex_lock (&player->priv->stream_list_lock);
 
 		if (playing) {
 			/* wait for current stream's EOS */
@@ -2258,6 +2269,7 @@ actually_start_stream (RBXFadeStream *stream, GError **error)
 		 * thread..  hmm.
 		 */
 		GList *l;
+		GList *reap = NULL;
 		for (l = player->priv->streams; l != NULL; l = l->next) {
 			RBXFadeStream *pstream = (RBXFadeStream *)l->data;
 			if (pstream == stream)
@@ -2269,7 +2281,7 @@ actually_start_stream (RBXFadeStream *stream, GError **error)
 			case FADING_IN:
 				/* kill this one */
 				rb_debug ("stopping stream %s (replaced by new stream)", pstream->uri);
-				unlink_and_dispose_stream (player, pstream);
+				reap = g_list_prepend (reap, g_object_ref (pstream));
 				break;
 
 			default:
@@ -2278,6 +2290,15 @@ actually_start_stream (RBXFadeStream *stream, GError **error)
 			}
 		}
 
+		/* drop the stream list lock to remove the streams, otherwise deadlock */
+		g_static_rec_mutex_unlock (&player->priv->stream_list_lock);
+		for (l = reap; l != NULL; l = l->next) {
+			RBXFadeStream *pstream = (RBXFadeStream *)l->data;
+			unlink_and_dispose_stream (player, pstream);
+			g_object_unref (pstream);
+		}
+		g_static_rec_mutex_lock (&player->priv->stream_list_lock);
+
 		ret = link_and_unblock_stream (stream, error);
 	}
 
