I regularly reinstall Windows, so when I used iTunes, I had to make sure I knew how to back up my music library (because I didn't want to re-rate all my songs :D).  I recently switched back to Zune from iTunes because I got so frustrated with my cracked iPod Touch screen.  Then, came the invevitable reinstall :)

I keep my music on a separate partition, along with ALL my data (Folder Redirection for the win!), so the music files aren't the problem.  With iTunes I could place the music library database on the other drive too, but so far no luck there with the Zune software (I'm going to check out Junctions to see if that will work).  So, I resigned myself to digging through my AppData folder to see if I could find the stuff I needed.

For those who don't already know, the AppData folder, in Windows Vista is in: C:\Users\[UserName]\AppData.  This is where programs (should) store their per-user settings and configuration data.  Unfortunately (AFAIK) it's not possible to redirect this folder (like you can with Documents, Music, etc.). 

The Zune software stores its settings in C:\Users\[UserName]\AppData\Local\Microsoft\Zune.  All I had to do was copy this folder over to my second partition, reinstall the OS and reinstall the Zune software.  Then, I started the Zune software, just to be sure and shut it down again.  I copied the backed up folder back into place, restarted the Zune software and voila my library is back.  I was even able to reconnect my Zune and have it automatically recognize it and sync!

So, in summary:

1. Back up C:\Users\[UserName]\AppData\Local\Microsoft\Zune
2. Reinstall Windows and other Apps
   
3. Reinstall Zune
4. Start Zune software (not sure if it's necessary, but it worked for me)
5. Shutdown Zune software
6. Copy backup back in to C:\Users\[UserName]\AppData\Local\Microsoft\Zune
7. Start Zune software and enjoy!

Let me know if that works for you, or if you have problems!