Are you sure it is out of warranty? I had a 2G 20gig go bad on me a few months ago and it was still under warranty so I just sent it back and they sent me a new (or refurbished) one.
I had the same problems you are reporting. I tried all the resets and the software restore, but the iPod never showed up in the software restore app. I think I even tried to run disk utility on it.
Anyway, check your receipt, if it is less than a year old, you are good to go!
-b