An iPod's disk format type may be an issue, but only for the "big" iPods. shuffles are always formatted using the Windows format, whether it is used on a Mac or a Windows PC. In fact, even those other iPod models can be formatted for Windows (using the "FAT" format) and they will still work on Mac. This is because Macs can read and write the Windows format used on iPods. (The opposite is not true; iPods used with a Windows PC must be formatted for Windows, because Windows cannot read the Mac format.)
However, the act of doing a Restore is a good thing to try. Unfortunately, you cannot do a Restore on the shuffle using your Mac, because iTunes does not see it. But if you can use your wife's PC, where it worked early, and do a Restore on the shuffle there, you can try that, and then connect it to your Mac. Doing a Restore erases the iPod and gives it a "fresh start," so it may solve the problem.
Therefore,
Other support pages in Apple suggest rebooting in safe mode and then using the disc utility to change the formatting on the shuffle from DOS Fat to an Apple format.
does not apply for the shuffle. However, you should try booting into Safe Mode
http://support.apple.com/kb/HT1455
Then, run Disk Utility to see of the shuffle's disk appears in the Disk Utility sidebar. If it does, that may suggest that you have an extension loading (maybe a third-party driver) when you start up normally that interferes with the shuffle being recognized. You don't need to take any action on the shuffle, just see if it appears in Disk Utility when starting up in Safe Mode.
Here are two other test I can think of trying, to help narrow down the cause...
Create a new user account in System Preferences Accounts pane. It can be an Admin or Standard account. I keep a "Test User" account for troubleshooting. Log out and log in to the new user account. Do not use Fast User Switching. In the new user account, try running iTunes and see if the shuffle is recognized. If it is, that may suggest that there is something in your usual user account that is causing this problem. It may be a user preferences setting that is corrupted, or a background process that is set to run automatically when you log in. If there is no change in the new user account, the cause is more likely to be at the system level (not related to a particular user account).
The other test is to start up using your Snow Leopard installation disc. Insert disc and restart with the C key held down. This takes you to the Installer screen. Go up to the menu bar, and under Utilities, select to run Disk Utility. If you connect the shuffle now, its disk should appear in the Disk Utility sidebar. If it does, the problem may be caused by a system-level issue in your current Snow Leopard installation.