Yeah, it's a bit confusing, but "Restore Deleted Media" is essentially "re-scan all my media". I don't think it actually restores anything, although I can't be 100% sure as I've only used that function once. And it's always a bit nerve-wracking to run something called "Restore Deleted Media" after you've carefully perfected all your meta-data...
Try this instead:
http://support.microsoft.com/kb/945319?sd=zune
Method two will force the software to re-index everything from scratch, which it seems is really what you want.
Let me know how it works out for you!
