Does the IP address start with 169 ? If so then that is a Self Assigned Auto IP address and won't do anything for you. What is the IP address you see ?
I had lots of WiFi trouble on my 4th gen Ipod when using it with a router (netgeat wgr614) ) that was setup to do WiFi B and G with WEP security. It wouldn't connect, would do a self assigned IP of 169.xxx.xxx.xxx In general I had all the problems you are getting. I tried all the solutions you tried.
So I turned off 'B' in the WiFi router and that helped to connect almost 100% of the time.
Then I picked up another WiFI router (wgt624 v3) that did 'N' as well, connected it the network, set it to 108N Auto, used WPA-PSK [TKIP] security and haven't ever had a problem.