Ok, I figured out what was going on. This is a pain, so I'll share what happened for people who store their music on a media server.
My computer lost connection with my media server. Zune didn't see the files for the music in my collection so it removed it from my device. It didn't matter if the licenses were up to date or anything. If it can't see it in your collection, you can't have it on your device aparently.
The moral is if you store your music on a media server, make sure you're logged in to see it, and if you unexpectedly lose connection, you'll have to wait for Zune to remove your entire connection and later wait for Zune to re-transfer your entire collectoin.