Apple has released iPod Reset Utility 1.0.3 for Mac and Windows.
Use iPod Reset Utility to restore the following iPod models back to their factory settings, when iTunes is unable to do so:
iPod shuffle (1st Generation)
iPod shuffle (2nd Generation)
The restore process completely erases all music and data on your iPod, and installs current iPod software on it.
Apple has also posted a support article with more information.