Your going to have to call your service provider to have them take a look either at your area or recent activity in your area for the service issues.
(As a trick I would try dialing *22800 - *22805 as with windows mobile phones if it can detect a signal from a roaming carrier it will sometimes revert your phone signal back to the original carrier and then no issue at that point. These will call different carriers programing which you NEVER need to complete but just call to get operator (some codes dont work in certain areas so dont fret if it just hangs up ))
That being said theres a good chance it can still fail. IF you ever get enough signal for an OTA then thats when you may need to get yourself an A-Key (which even when you have one or add one wont show in EPST)
That would be an authentication issue that appears with windows mobile when flashing or hard resetting a phone. Again you would normally have to call your service provider to even get a new correct A-Key anyways.
If all else fails try to relock your phone and program it to see how it goes. That will let you know if its truely an area issue or a phone issue. If it doesnt work once relocked then you can take it that the phone is ok and will need to have your carrier investigate your signal in the area. If it is working at that point then try to reflash it later on. if its only your pda and there are others that dont report the problem then try to have your carrier replace your relocked phone (if you dont feel bad about sending in a phone you KNOW you flashed at one point.
)
Anyways good luck and hope this helps.