That's not even close to being the "same issue," since you can see your shuffle in iTunes, and can even do a Restore on it. 🙂
A 2nd (or 1st) gen shuffle always uses manual loading of content. There is no automatic Sync Music setting for it, like on newer shuffles and the "big" iPods. iTunes treats your shuffle like it's a playlist in your iTunes library. You load it by manually dragging songs (in iTunes) from your music library to your shuffle in the sidebar, like you would to add songs to a playlist. You can also manually remove songs from that list.
There's also a feature called Autofill (available with all iPods). You can tell iTunes to fill iPod from your music library or a selected playlist. To use this feature, show iPod's song list from its settings screen in iTunes. The screenshot below is for a 1st gen shuffle; 2nd gen works the same way.

After showing the shuffle's Summary settings screen (where you did the Restore), click On This iPod (in the sidebar) to show this screen. Controls for Autofill are below shuffle's list of songs. Click Settings button to set up Autofill. Mine is set like this

You can choose to Autofill From your music library, or from a selected playlist. If the selected source has more songs than can fit on iPod, iTunes selects songs randomly to completely fill iPod. Click Autofill button to begin loading.