Q: I've done every step, and even restared my computer a few times and I still can't restore my iPod. Help!?

What happens when you  try to restore? Error message?

Duh. What does the error message say?

Unable to contact the iOS software update server gs.apple.com

Error 1004, 1013, 1638, 3014, 3194: These errors may be the result of the connection to gs.apple.com being redirected or blocked. Follow these steps to resolve these errors:

1. Install the latest version of iTunes.
2. Check security software. Ensure that communication to gs.apple.com is allowed. Follow this article for assistance with security software. iTunes for Windows: Troubleshooting security software issues.
3. Check the hosts file. The restore will fail if there is an active entry to redirect gs.apple.com. Follow iTunes: Advanced iTunes Store troubleshooting to edit the hosts file or revert to a default hosts file. See section "Blocked by configuration: (Mac OS X/Windows) > Rebuild network information".
4. Try to restore from another known-good computer and network.
5. If the errors persist on another computer, the device may need service.

So you tried another computer?

So you  also went to the Genius at the Apple store (the article said the device may need service.)