Currently Being ModeratedOct 4, 2012 8:10 AM (in response to CjClarke)
I had the same problem since the iOS 6 update.
I asked around and tried everything including hard reset and restore with no luck.
Then someone suggested to try resetting the network... WOW. It is fixed now.
Go to: Settings > General > Reset (all the way at the bottom) > Reset Network Settings
Hope this works for you.