Alright, this is a pretty easy fix.
Hold Back-Up to reset the Zune
Hold Back-Center-Left to erase all content, as well as the firmware. If you have a flash based Zune, use Back-Center-Play
Connect to the computer to reload the firmware and media
It shouldn't ever do that again after doing this.