Hopped on with Apple Support today and sort of got a fix, albeit a very tedious and time consuming one.
Below are the various troubleshoots that the rep took me through ranging from par for the course and "I'm desperate":
1. Turn off Cellular Data, restart your phone (hold Home and Lock together), Turn on Cellular Data
2. Create a backup of your iPhone with iTunes, then Navigate to Settings > General > Reset > Reset All Settings
3. Create a backup of your iPhone, make sure iTunes is up to date on your computer, go to the main screen for your device in iTunes and click Restore iPhone (this will re-install the OS and also erase all your data), set up as a new iPhone when prompted, check to see if the issue persists, if it doesn't, you can try to restore your back-up. If the issue persists after your back-up then you may have some corrupted files there.
4. Sync all of your photos, contacts, calendar, etc. (any data you would like to get back onto your phone; some apps like WhatsApp also have an option to back-up chat history) to iCloud, go to the main screen for your device in iTunes and click Restore iPhone (this will re-install the OS and also erase all your data), set up as a new iPhone when prompted, retrieve and sync all of your photos, contacts, calendar, etc. from iCloud. Unfortunately, you will have to manually download and install your apps.
It took me to #4 to fix the issue. Long tedious process but better fixed then blowing through all my data and not being able to do anything about it!
