iPhone EDGE Network Problem
The last thing you can try to do before sending it to repair is making a new install by Erasing All Content and Settings. There are many ways to accomplish this and many layers of wiping. One of them is through installing a new firmware (ipsw) file just in case the one iTunes download is somehow corrupted.

But doing anything beyond the regular Apple way is entirely up to you as the process are even more time consuming and not all that simple.