I'm having better luck now, but it's not been easy. Here's the steps I've taken to get things back in shape -
I should point out that I did select "replace all media information" on the install. This was probably a bad idea, but now it seems to have helped correct the info. If you selected this as well and have seen your meta data get hosed, try these step and leave the option checked.
1) Do the database delete thing on the first page of comments in this thread
2) Luanch Zune 2.0 let it bake for a long time (15-20 minutes for me)
3) Closed Zune, deleted ZuneStore.sdf, and re-opened
4) Let Zune bake for a long time
(3&4 are optional if after step 2 things are looking good in your meta data)
In my case, at this point most (not all) of the problems were in the db, not my meta data. The meta data had managed to get updated and fixed for the most part after step 4. (I actually watched it update a few mp3's in explorer so I know it was working on it.
To fix miss tagged mp3s and miss categorized artists:
1) Find mixed blocks of albums/artists in Zune 2.0 (All the J's for example, or two artists that are mixed up)
2) drag those artist folders out someplace where they are not watched by Zune 2.0 and let the db update
3) Mass-fix album or artist problems by selecting the effected mp3s (right click -> properties - > details) or mass-delete incorrect meta data by clearing fields if needed
4) drag and drop each artist or album folder back into your library one at a time and let 2.0 update it's db
That's got me back to about 98% correct. I'm sure I'll find a few mistakes here and there as I go but I'm back on track for the most part using these mothods.
Overall - WHEW! MS, guys, come on, this is going to get ugly if you don't track it down. For what it's worth, I love the new software, it's really nice. But damn. That was not the way I was expecting things to start off.