diff --git a/src/Core/Banshee.Core/Banshee.Base/CoverArtSpec.cs b/src/Core/Banshee.Core/Banshee.Base/CoverArtSpec.cs
index 2b676f2..4340e3b 100644
--- a/src/Core/Banshee.Core/Banshee.Base/CoverArtSpec.cs
+++ b/src/Core/Banshee.Core/Banshee.Base/CoverArtSpec.cs
@@ -28,6 +28,8 @@
 
 using System;
 using System.IO;
+using System.Collections.Generic;
+using System.Text;
 using System.Text.RegularExpressions;
 
 using Mono.Unix;
@@ -85,25 +87,61 @@ namespace Banshee.Base
 
         public static string CreateArtistAlbumId (string artist, string album)
         {
-            return CreateArtistAlbumId (artist, album, false);
+            if (artist == unknown_artist || artist == unknown_artist_tr || album == unknown_album || album == unknown_album_tr) {
+                return null;
+            }
+
+            string digestible = String.Format ("{0}\t{1}", artist ?? "", album ?? "");
+
+            return String.Format ("album-{0}", Digest (digestible));
         }
 
-        public static string CreateArtistAlbumId (string artist, string album, bool asUriPart)
+        public static string Digest (string str)
+        {
+            if (String.IsNullOrEmpty (str)) {
+                return null;
+            }
+
+            str = str.Normalize (NormalizationForm.FormKD);
+            return Hyena.CryptoUtil.Md5Encode (str, Encoding.UTF8);
+        }
+
+        static CoverArtSpec () {
+            Hyena.Log.DebugFormat ("Album artwork path set to {0}", root_path);
+        }
+
+        private static string root_path = Path.Combine (XdgBaseDirectorySpec.GetUserDirectory (
+            "XDG_CACHE_HOME", ".cache"),  "media-art");
+
+        public static string RootPath {
+            get { return root_path; }
+        }
+
+        #region Old spec
+
+        private static string legacy_root_path = Path.Combine (XdgBaseDirectorySpec.GetUserDirectory (
+            "XDG_CACHE_HOME", ".cache"),  "album-art");
+
+        public static string LegacyRootPath {
+            get { return legacy_root_path; }
+        }
+
+        public static string CreateLegacyArtistAlbumId (string artist, string album)
         {
             if (artist == unknown_artist || artist == unknown_artist_tr || album == unknown_album || album == unknown_album_tr) {
                 return null;
             }
 
-            string sm_artist = EscapePart (artist);
-            string sm_album = EscapePart (album);
+            string sm_artist = LegacyEscapePart (artist);
+            string sm_album = LegacyEscapePart (album);
 
             return String.IsNullOrEmpty (sm_artist) || String.IsNullOrEmpty (sm_album)
                 ? null
-                : String.Format ("{0}{1}{2}", sm_artist, asUriPart ? "/" : "-", sm_album);
+                : String.Format ("{0}{1}{2}", sm_artist, "-", sm_album);
         }
 
-        private static Regex filter_regex = new Regex (@"[^A-Za-z0-9]*", RegexOptions.Compiled);
-        public static string EscapePart (string part)
+        private static Regex legacy_filter_regex = new Regex (@"[^A-Za-z0-9]*", RegexOptions.Compiled);
+        public static string LegacyEscapePart (string part)
         {
             if (String.IsNullOrEmpty (part)) {
                 return null;
@@ -113,19 +151,9 @@ namespace Banshee.Base
             if (lp_index > 0) {
                 part = part.Substring (0, lp_index);
             }
-
-            return filter_regex.Replace (part, "").ToLower ();
-        }
-
-        private static string root_path = Path.Combine (XdgBaseDirectorySpec.GetUserDirectory (
-            "XDG_CACHE_HOME", ".cache"),  "album-art");
-
-        static CoverArtSpec () {
-            Hyena.Log.DebugFormat ("Album artwork path set to {0}", root_path);
+            return legacy_filter_regex.Replace (part, "").ToLower ();
         }
 
-        public static string RootPath {
-            get { return root_path; }
-        }
+        #endregion Old spec
     }
 }
diff --git a/src/Core/Banshee.Core/Banshee.Base/Tests/CoverArtSpecTests.cs b/src/Core/Banshee.Core/Banshee.Base/Tests/CoverArtSpecTests.cs
index 5335c3d..25f2dbb 100644
--- a/src/Core/Banshee.Core/Banshee.Base/Tests/CoverArtSpecTests.cs
+++ b/src/Core/Banshee.Core/Banshee.Base/Tests/CoverArtSpecTests.cs
@@ -34,59 +34,41 @@ using Banshee.Base;
 namespace Banshee.Base.Tests
 {
     [TestFixture]
-    public class EscapePartTests
+    public class DigestPartTests
     {
-        private void AssertEscaped (string original, string expected)
+        private void AssertDigested (string original, string expected)
         {
-            Assert.AreEqual (expected, CoverArtSpec.EscapePart (original));
+            Assert.AreEqual (expected, CoverArtSpec.Digest (original));
         }
 
         [Test]
         public void TestEmpty ()
         {
-            AssertEscaped (null, null);
-            AssertEscaped ("", null);
+            AssertDigested (null, null);
+            AssertDigested ("", null);
+            AssertDigested (" ", "7215ee9c7d9dc229d2921a40e899ec5f");
         }
 
         [Test]
-        public void TestLowercased ()
+        public void TestUnicode ()
         {
-            AssertEscaped ("A", "a");
+            AssertDigested ("\u00e9", "5526861fbb1e71a1bda6ac364310a807");
+            AssertDigested ("e\u0301", "5526861fbb1e71a1bda6ac364310a807");
         }
 
         [Test]
-        public void TestUnwanted ()
+        public void TestEscaped ()
         {
-            // Part of the in-progress media art storage spec
-            AssertEscaped ("!", "");
-            AssertEscaped ("@", "");
-            AssertEscaped ("#", "");
-            AssertEscaped ("$", "");
-            AssertEscaped ("^", "");
-            AssertEscaped ("&", "");
-            AssertEscaped ("*", "");
-            AssertEscaped ("_", "");
-            AssertEscaped ("+", "");
-            AssertEscaped ("=", "");
-            AssertEscaped ("|", "");
-            AssertEscaped ("\\", "");
-            AssertEscaped ("/", "");
-            AssertEscaped ("?", "");
-            AssertEscaped ("~", "");
-            AssertEscaped ("`", "");
-            AssertEscaped ("'", "");
-            AssertEscaped ("\"", "");
-
-            // Banshee-specific: strip *everything* non-ASCII
-            AssertEscaped ("\u00e9toile", "toile");
-            AssertEscaped ("e\u0301", "e");
+            AssertDigested ("(a)", "69dfdf4e6a7c8489262f9d8b9958c9b3");
         }
 
         [Test]
-        public void TestStripNotes ()
+        public void TestExamples ()
         {
-            AssertEscaped ("a(b)cd", "a");
-            AssertEscaped ("a(b)c(d)e", "abc");
+            AssertDigested ("Metallica", "8b0ee5a501cef4a5699fd3b2d4549e8f");
+            AssertDigested ("And Justice For All", "17e81b0a8cc3038f346e809fccda207d");
+            AssertDigested ("Radio ga ga", "baad45f3f55461478cf25e3221f4f40d");
+            AssertDigested ("World Soccer", "cd678d70c5c329759a7a7b476f7c71b1");
         }
     }
 }
diff --git a/src/Core/Banshee.Core/Banshee.Core.csproj b/src/Core/Banshee.Core/Banshee.Core.csproj
index 6292653..d9e3088 100644
--- a/src/Core/Banshee.Core/Banshee.Core.csproj
+++ b/src/Core/Banshee.Core/Banshee.Core.csproj
@@ -24,6 +24,7 @@
     <WarningLevel>4</WarningLevel>
     <Optimize>false</Optimize>
     <OutputPath>..\..\..\bin</OutputPath>
+    <DefineConstants>ENABLE_TESTS</DefineConstants>
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Windows|AnyCPU' ">
     <DebugSymbols>true</DebugSymbols>
diff --git a/src/Core/Banshee.Services/Banshee.Metadata.Rhapsody/RhapsodyQueryJob.cs b/src/Core/Banshee.Services/Banshee.Metadata.Rhapsody/RhapsodyQueryJob.cs
index 02d42e2..4dfbdab 100644
--- a/src/Core/Banshee.Services/Banshee.Metadata.Rhapsody/RhapsodyQueryJob.cs
+++ b/src/Core/Banshee.Services/Banshee.Metadata.Rhapsody/RhapsodyQueryJob.cs
@@ -48,6 +48,19 @@ namespace Banshee.Metadata.Rhapsody
     {
         private static Uri base_uri = new Uri("http://www.rhapsody.com/");
 
+        private static Regex filter_regex = new Regex (@"[^A-Za-z0-9]*", RegexOptions.Compiled);
+        private static string EscapeUrlPart (string part)
+        {
+            return filter_regex.Replace (part, "").Replace (" ", "-").ToLower ();
+        }
+
+        private static string GetAlbumUrl (IBasicTrackInfo track)
+        {
+            string artist = EscapeUrlPart (track.AlbumArtist);
+            string album = EscapeUrlPart (track.AlbumTitle);
+            return String.Format ("{0}/{1}", artist, album);
+        }
+
         public RhapsodyQueryJob(IBasicTrackInfo track)
         {
             Track = track;
@@ -65,7 +78,7 @@ namespace Banshee.Metadata.Rhapsody
                 return;
             }
 
-            Uri data_uri = new Uri(base_uri, String.Format("/{0}/data.xml", artwork_id.Replace('-', '/')));
+            Uri data_uri = new Uri(base_uri, String.Format("/{0}/data.xml", GetAlbumUrl (Track)));
 
             XmlDocument doc = new XmlDocument();
             HttpWebResponse response = GetHttpStream (data_uri);
diff --git a/src/Core/Banshee.ThickClient/Banshee.Collection.Gui/ArtworkManager.cs b/src/Core/Banshee.ThickClient/Banshee.Collection.Gui/ArtworkManager.cs
index 90b5577..5a0c518 100644
--- a/src/Core/Banshee.ThickClient/Banshee.Collection.Gui/ArtworkManager.cs
+++ b/src/Core/Banshee.ThickClient/Banshee.Collection.Gui/ArtworkManager.cs
@@ -37,6 +37,7 @@ using Gdk;
 using Hyena;
 using Hyena.Gui;
 using Hyena.Collections;
+using Hyena.Data.Sqlite;
 
 using Banshee.Base;
 using Banshee.IO;
@@ -254,7 +255,7 @@ namespace Banshee.Collection.Gui
 
 #region Cache Directory Versioning/Migration
 
-        private const int CUR_VERSION = 2;
+        private const int CUR_VERSION = 3;
         private void MigrateCacheDir ()
         {
             int version = CacheVersion;
@@ -262,16 +263,16 @@ namespace Banshee.Collection.Gui
                 return;
             }
 
-            var root_path = CoverArtSpec.RootPath;
+            var legacy_root_path = CoverArtSpec.LegacyRootPath;
 
             if (version < 1) {
                 string legacy_artwork_path = Paths.Combine (Paths.LegacyApplicationData, "covers");
 
-                if (!Directory.Exists (root_path)) {
-                    Directory.Create (CoverArtSpec.RootPath);
+                if (!Directory.Exists (legacy_root_path)) {
+                    Directory.Create (legacy_root_path);
 
                     if (Directory.Exists (legacy_artwork_path)) {
-                        Directory.Move (new SafeUri (legacy_artwork_path), new SafeUri (root_path));
+                        Directory.Move (new SafeUri (legacy_artwork_path), new SafeUri (legacy_root_path));
                     }
                 }
 
@@ -283,7 +284,7 @@ namespace Banshee.Collection.Gui
 
             if (version < 2) {
                 int deleted = 0;
-                foreach (string dir in Directory.GetDirectories (root_path)) {
+                foreach (string dir in Directory.GetDirectories (legacy_root_path)) {
                     int size;
                     string dirname = System.IO.Path.GetFileName (dir);
                     if (Int32.TryParse (dirname, out size) && !IsCachedSize (size)) {
@@ -297,14 +298,84 @@ namespace Banshee.Collection.Gui
                 }
             }
 
+            if (version < 3) {
+                Log.Information ("Migrating album-art cache directory");
+                var started = DateTime.Now;
+                int count = 0;
+
+                var root_path = CoverArtSpec.RootPath;
+                if (!Directory.Exists (root_path)) {
+                    Directory.Create (root_path);
+                }
+
+                string sql = "SELECT Title, ArtistName FROM CoreAlbums";
+                using (var reader = new HyenaDataReader (ServiceManager.DbConnection.Query (sql))) {
+                    while (reader.Read ()) {
+                        var album = reader.Get<string>(0);
+                        var artist = reader.Get<string>(1);
+                        var old_file = CoverArtSpec.CreateLegacyArtistAlbumId (artist, album);
+                        var new_file = CoverArtSpec.CreateArtistAlbumId (artist, album);
+
+                        if (String.IsNullOrEmpty (old_file) || String.IsNullOrEmpty (new_file)) {
+                            continue;
+                        }
+
+                        old_file = String.Format ("{0}.jpg", old_file);
+                        new_file = String.Format ("{0}.jpg", new_file);
+
+                        var old_path = new SafeUri (Paths.Combine (legacy_root_path, old_file));
+                        var new_path = new SafeUri (Paths.Combine (root_path, new_file));
+
+                        if (Banshee.IO.File.Exists (old_path) && !Banshee.IO.File.Exists (new_path)) {
+                            Banshee.IO.File.Move (old_path, new_path);
+                            count++;
+                        }
+                    }
+                }
+
+                if (ServiceManager.DbConnection.TableExists ("PodcastSyndications")) {
+                    sql = "SELECT Title FROM PodcastSyndications";
+                    foreach (var title in ServiceManager.DbConnection.QueryEnumerable<string> (sql)) {
+                        var old_digest = CoverArtSpec.LegacyEscapePart (title);
+                        var new_digest = CoverArtSpec.Digest (title);
+
+                        if (String.IsNullOrEmpty (old_digest) || String.IsNullOrEmpty (new_digest)) {
+                            continue;
+                        }
+
+                        var old_file = String.Format ("podcast-{0}.jpg", old_digest);
+                        var new_file = String.Format ("podcast-{0}.jpg", new_digest);
+
+                        var old_path = new SafeUri (Paths.Combine (legacy_root_path, old_file));
+                        var new_path = new SafeUri (Paths.Combine (root_path, new_file));
+
+                        if (Banshee.IO.File.Exists (old_path) && !Banshee.IO.File.Exists (new_path)) {
+                            Banshee.IO.File.Copy (old_path, new_path, false);
+                            count++;
+                        }
+                    }
+                }
+
+                Directory.Delete (legacy_root_path, true);
+                Log.InformationFormat ("Migrated {0} files in {1}s", count, DateTime.Now.Subtract(started).TotalSeconds);
+            }
+
             CacheVersion = CUR_VERSION;
         }
 
         private static SafeUri cache_version_file = new SafeUri (Paths.Combine (CoverArtSpec.RootPath, ".cache_version"));
         private static int CacheVersion {
             get {
-                if (Banshee.IO.File.Exists (cache_version_file)) {
-                    using (var reader = new System.IO.StreamReader (Banshee.IO.File.OpenRead (cache_version_file))) {
+                var file = cache_version_file;
+                if (!Banshee.IO.File.Exists (file)) {
+                    file = new SafeUri (Paths.Combine (CoverArtSpec.LegacyRootPath, ".cache_version"));
+                    if (!Banshee.IO.File.Exists (file)) {
+                        file = null;
+                    }
+                }
+
+                if (file != null) {
+                    using (var reader = new System.IO.StreamReader (Banshee.IO.File.OpenRead (file))) {
                         int version;
                         if (Int32.TryParse (reader.ReadLine (), out version)) {
                             return version;
diff --git a/src/Dap/Banshee.Dap.MassStorage/Banshee.Dap.MassStorage/MassStorageSource.cs b/src/Dap/Banshee.Dap.MassStorage/Banshee.Dap.MassStorage/MassStorageSource.cs
index 3e687c6..aa48186 100644
--- a/src/Dap/Banshee.Dap.MassStorage/Banshee.Dap.MassStorage/MassStorageSource.cs
+++ b/src/Dap/Banshee.Dap.MassStorage/Banshee.Dap.MassStorage/MassStorageSource.cs
@@ -509,12 +509,7 @@ namespace Banshee.Dap.MassStorage
                     !String.IsNullOrEmpty (CoverArtFileName) && (FolderDepth == -1 || FolderDepth > 0)) {
                 SafeUri cover_uri = new SafeUri (System.IO.Path.Combine (System.IO.Path.GetDirectoryName (new_uri.LocalPath),
                                                                          CoverArtFileName));
-                string coverart_id;
-                if (track.HasAttribute (TrackMediaAttributes.Podcast)) {
-                    coverart_id = String.Format ("podcast-{0}", Banshee.Base.CoverArtSpec.EscapePart (track.AlbumTitle));
-                } else {
-                    coverart_id = track.ArtworkId;
-                }
+                string coverart_id = track.ArtworkId;
 
                 if (!File.Exists (cover_uri) && CoverArtSpec.CoverExists (coverart_id)) {
                     Gdk.Pixbuf pic = null;
diff --git a/src/Extensions/Banshee.Podcasting/Banshee.Podcasting/PodcastService.cs b/src/Extensions/Banshee.Podcasting/Banshee.Podcasting/PodcastService.cs
index 01b3cbc..9fc9987 100644
--- a/src/Extensions/Banshee.Podcasting/Banshee.Podcasting/PodcastService.cs
+++ b/src/Extensions/Banshee.Podcasting/Banshee.Podcasting/PodcastService.cs
@@ -608,7 +608,8 @@ namespace Banshee.Podcasting
 
         public static string ArtworkIdFor (Feed feed)
         {
-            return String.Format ("podcast-{0}", Banshee.Base.CoverArtSpec.EscapePart (feed.Title));
+            string digest = Banshee.Base.CoverArtSpec.Digest (feed.Title);
+            return digest == null ? null : String.Format ("podcast-{0}", digest);
         }
 
         // Via Monopod
