Since you are able to start the Restore process (before the error occurs), the shuffle appears in iTunes when connected, correct?
Before starting Restore process, if Enable disk use is currently not enable, checkmark that box and click Apply. The Enable disk use checkbox is on shuffle's Summary settings screen (same screen as Restore button). When disk use is enabled, the shuffle's disk is already mounted by the system before the Restore process begins. That may help with error.
If that does not help, shut down (power off) the Mac. Disconnect all USB devices. You can leave standard USB keyboard/mouse connected, if used. If your Mac is a laptop, connect its power adapter (so it's not running on battery power). Put shuffle's power switch in the OFF position. Start up Mac, run iTunes, and connect shuffle to a direct USB port, by itself. Then, immediately try doing a Restore again.