1. Quit Recent Tunes from the menu bar
2. Open up Apples “Property List Editor.” (you must have Apples Developers Tools installed - Link for more info)
3. In Property List Editor open up the Recent Tunes pref file, com.freshsqueeze.recenttunes.plist , located in your home pref folder.
4. once open, look for “RT2.0SongList”. This is an Array. Click the drop down triang;e to expand this array and notice the “Dictionary” entries which are listed as 0,1,2,3 … etc
5. DELETE all of these “dictionary” sub-elements.
6. Quit Property List Editor and Re-Launch Recent Tunes Start Pumping some iTune’s and hopefully you’re good to go!

This has worked for me now numerous times no for me, so hope fully it will for others. I’ve also noted in my experimenting that the failure of Recent Tunes seems to occur after the App itself has been Quit. I;ve Also noted that the here forementioned preference file is only written to (ie new tracks written to file) after Recent Tunes quiting…