If it still shows up in Windows as a USB device, that's good... Did this shuffle previously work with that laptop, and it does not work now for some reason? Or is this the first time you are connecting this shuffle to that computer?
As a test, shut down (power off) your computer. Disconnect all USB devices, including USB hub. Do this to Reset your shuffle.
Start up computer. Run iTunes. Connect shuffle. If the shuffle is recognized by iTunes, try doing a Restore again.
I asked earlier, but I'll assume this worked fine before (with that computer) and it is not working now for some reason. If this is the first time you are trying to use this shuffle with that computer, let me know...
Since you can do a Restore in iTunes, the shuffle must be appearing in the iTunes sidebar, under DEVICES. When you select the shuffle in the sidebar, and go to the Settings tab over to the right, that screen is where the Restore button is located. Look for a checkbox setting there that says Enable disk use. If it is currently NOT checked (which is the default setting), check it and Apply the change.
The shuffle should now appear to Windows (as a "disk") all the time, when it is connected. Try doing a Restore again.
Im not entirely sure if ive used it with this computer (ive swapped computers alot recently) Ive used other ipods on this one and not had a problem though. Its appearing in the sidebar but when selected only comes up with a summary screen in which my only option is to restore, it wont let me do anything else yet the restore is just not working.
If one of the "other iPods" happens to be a 4th gen shuffle, make sure you are NOT using the USB cable that comes with the 4th gen shuffle on a 2nd gen shuffle (which came with a cable that has a "mini-dock" at the shuffle end). Their connectors are different. Actually, I don't think you would even get it to appear in iTunes at all (to try a Restore), but I thought I'd check the possibility...
When you have it connected with iTunes NOT running, does it appear in Windows (as a storage device or in device manager)?
I have two suggestions. There is an iPod Reset Utility
that is only for the 1st and 2nd gen shuffle. It does something like a Restore in iTunes, but works at a "lower" level in cases when a Restore in iTunes does not work (or cannot be used). For it to work, the shuffle does need to be seen by the system, and it sounds like yours meets that requirement.
Unfortunately, I don't think it works with Windows 7. If you happen to have an older PC with 32-bit Windows, you can use that PC to run the utility on the shuffle. Or, maybe you have a friend with a Mac or 32-bit Windows PC that can run it for your. Or, if you have an Apple Store nearby, you can make a reservation at the Genius Bar and ask them to look at it and run the reset utility.
The second suggestion, if you don't have a convenient way to use the reset utility, is to use Windows to reformat the shuffle's storage like it was a flash drive. Use a "full" format (not the "quick" option). Use the "FAT" format type. Make sure iTunes is NOT running. After it is reformatted, it will be blank. When you run iTunes, it should recognize the shuffle and ask you to Restore it (to re-install the software and set it to default settings). Hopefully, it will work this time.