Index: rb-ipod-source.c
===================================================================
--- rb-ipod-source.c	(revision 4984)
+++ rb-ipod-source.c	(working copy)
@@ -885,7 +885,7 @@
 }
 
 static void
-remove_track_from_db (Itdb_Track *track)
+remove_track_from_db (Itdb_Track *track, RBiPodSource *source)
 {
 	GList *it;
 
@@ -893,6 +893,12 @@
 		itdb_playlist_remove_track ((Itdb_Playlist *)it->data, track);
 	}
 	itdb_track_remove (track);
+
+	RBiPodSourcePrivate *priv = IPOD_SOURCE_GET_PRIVATE (source);
+	if (priv->needs_shuffle_db) {
+		itdb_shuffle_write (priv->ipod_db, NULL);
+	}	
+
 }
 
 static void
@@ -922,7 +928,7 @@
 			continue;
 		}
 
- 		remove_track_from_db (track);
+ 		remove_track_from_db (track, source);
 		g_hash_table_remove (priv->entry_map, entry);
 		rhythmdb_entry_move_to_trash (db, entry);
 		rhythmdb_commit (db);
