For what it's worth, when I first got my phone I did the Reset Network Settings thing many times without issue. Granted, that wasn't on 1.1.2 - YMMV. Perhaps there's a legit bug in there now. Who knows? 😕
Regarding not getting to EDGE - sometimes my iPhone, and even my Nokia phone before it, would stop communicating with the cell network altogether. Calls wouldn't work, neither would data. A power-cycle always fixed it. My theory is that after several weeks of being turned on, if something's changed at the service end of things, the phone isn't able to continue with its connection, and the only solution is to establish a new one from scratch. Or perhaps there's an overflow bug somewhere after a certain amount of time/data. Dunno.