I went to the Apple Genius bar yesterday and I was calm and just explained that I did not have AppleCare but have had no problems w/phone until I put iOS4 on it. Also told him everything I had tried to do to get it working again. He checked it out, did something to it (also helping someone else w/their MacBook), asked if he could take it to back to open it and check it out. He came back with a new iPhone 3G!!

I didn't have to make a fuss at all! ...my guess is they know there is an issue (he said iOS4 may have inadvertently turned wifi off) ... in any case I have a new working iPhone 3G w/3.1.3 OS on it, and it will stay that way until 4.1 comes out. The biggest thing I notice is that GPS sucks...they improved the algorithm in iOS 4 for location services (or the GPS function)...all my apps that use this worked better in iOS4, but I'm not taking any chances-keeping 3.1.3 for now.
For those of you that have iOS 4 on iPhone 3G and only problem is it is slow, he did mention that, if you turn off spotlight search it will act normally instead of being slow.
I'm thinking they have an overstock of iPhone 3G since they no longer sell it, they are worth nothing to them, and to give me a new one is probably a tax write off. (now I can wait 6 months until I get full discount for upgrade to iPhone4)
(I know this does not help if you have jailbroken your phone, but if you have jailbroken your iPhone 3G, do not update to iOS4 until 4.1 comes out!).
I am only referring to iPhone 3G, not iPhone 3Gs.