My 2G iPod touch must be more possessed than Marilyn Manson... location services ONLY started working for me after upgrading to iOS4. On 3.1.3, it would work on occasion but rarely. It worked a few times in downtown Chattanooga, TN and at McDonalds in Orlando, FL (although Maps sent me to the wrong Pizza Hut), but I hadn't managed to get it to work in Augusta, GA. The one time it actually picked up a location, it said I was in Richmond, VA.
After upgrading, I opened Maps, hit the location button, and it worked like a charm. Nailed it too, almost dead center on my house. It seems odd to me that a lot of people are having issues with it. Guess I got lucky.
These might seem like obvious troubleshooting questions, but you'd be surprised what people overlook (is the computer plugged in? no...). Is location services enabled in Settings? Have you jailbroken it? Tried restoring the firmware? Tried it on another WiFi network? Hopefully it's just something little that people are overlooking that was set by default in iOS 3 but disabled in 4. Good luck with fixing it though.