I was finally able to resolve the issue after contacting Apple Technical Support
These are the steps:
1. Perform backup of my iPhone on My Computer using iTunes.
2. Turn off Find my iPhone
3. Erase iPhone and all Settings
THIS IS THE IMPORTANT PART
4. Upon reboot, do not sign into your iCloud or iTunes Account.
5. Set up as new iphone, log into wifi, wait for phone to fully boot as brand new.
6. Once iPhone notification comes up saying that it is activated, the 3G should be working as it should normally be operating.
7. Download your iPhone backup back onto your phone.
8. Everything should be functioning properly!
Hope this helps!