Are you connecting to a WiFi network or using mobile data (cellular) when this error message occurs? Or does it happen when using both?
If just WiFi, try rebooting your router -- it could just be a local network glitch. Try connecting to a different WiFi network, like at a friend's home or work. If you have the same problem with a different WiFi network that indicates the problem is more likely to be with your phone.
If just mobile data, try re-seating your SIM card. It might also be helpful to log into your account with your carrier to check that your service is still active.