Between me and my brother, we had three iPod Shuffle that iTunes wouldn't see, nor the previous iPod reset utility. They where pretty much dead.
Apple released a new version of the iPod Reset Utility, and this latest version (1.0.2) was able to recover all of our iPod's.
So if your Shuffle is not recognized by your iTunes, check out this latest version. It worked for us.