It is not unexpected for enterprise networks to run web security proxies that inspect encrypted traffic when given a reason to suspect something problematic. This allows them to detect encrypted malware and prevent it from infecting you. (It also allows them to restrict other content, such as porn or some other policy enforcement that is not related to security.)
I haven't heard of this for consumer-grade networks though. This is very disappointing and I suggest either finding another provider or at least using a VPN to tunnel your traffic through another location that does not inspect your encrypted data in this manner.
If you don't get the error any more (as noted in the comments above), contact technical support and ask about it. Perhaps something (e.g. DNS) was merely misconfigured, or perhaps the threshold for a "reason to suspect" your traffic was too aggressive. If they're wise, they should apologize profusely and try to win back your trust.
livebox ssl
suggests that the Livebox Orange type router does indeed do some kind of SSL interception. But my French isn't good enough to actually make sense of it.