I had that problem once.
I went into Settings and switched off the Internet Connection and switched it back on and nothing happens and it just says connection failed. This was at night before bed, so I switched it off for one last time and switched it on again and left the phone for the night. Woke up and the internet worked again.
So I suggest you switch off the internet, turn it back on and wait. It worked for me.