I've had a similar experience. If pulling the battery doesn't resolve it, then it's almost always a problem with the service in your area (Cingular Infrastructure).
Whenever I've called them about, they claim no outages, and give me the run-around about a device probelm.
I finally learned my lesson. When this happens I check with other users around me to see if they lose EDGE coverage. If they do, then I call the local Cingular store, have them check it with their phones. When they see it's down, they initiate a call! Works every time.
I've lost EDGE service for 4-6 hours sometimes.
Bob
