That old "Reset Utility" is ONLY for the 1st and 2nd gen iPod shuffle, which had some issues that prevented using the standard Restore in iTunes, so Apple release that utility. It was released when Windows XP was the latest version of Window; it does not work with Windows 7. But it would not help you if your shuffle is 4th gen.
When you say "reset," are you trying to do a Restore on the shuffle in iTunes, from the shuffle's Summary tab? When does that error message appear, exactly?