Lost all iTunes playlists

This is a wild one. One of my clients using iTunes on an iMac has lost his (many) playlists.  Details:

1. Very large iTunes collection (approx 300GB). Many custom playlists (don't know how many)

2. A couple of weeks ago, he started iTunes and says "some music and all playlists are gone"  The "some music" appears to be purchased music (most of his collection is his ripped CDs).

3. Before I had a chance to do the standard XML file manipulations to re-import his playlists, he says he found a shortcut to his external USB drive which contained an iTunes folder, and dragged the iTunes Music folder right into his running iTunes.  He says this caused his music to appear (complete, as far as he can tell).  I told him that this was not a good idea, as this may affect his playlists.  He confirmed that his playlists were still missing.

4. I ran the standard fix of attempting to re-import his iTunes Music Library.xml file, but it gives an error saying that some playlists could not be imported because the music is missing.  The result is that all the standard iTunes lists are there, but none of his own custom lists.

Is there any hope of restoring his collection?  He apparently didn't have a time machine backup, though he did use Carbonite (none of his iTunes files are on Carbonite as far as I can tell).

Thanks.
Dave