One suggestion I found was to delete all Keychain entries for FaceTime. Since it didn't seem to match the error message about Network connection, I dismissed it for the time being.
When all other suggestions, resetting router etc, failed, I went the Keychain entry deletion way and it worked for me.
In Keychain, I entered Facetime into the search field. I deleted all the entries that appeared. Started up FaceTime and manually logged in. There was a short sequence of operations to get the account set up again. Next time I started Facetime it was all automatic and working fine. I don't know what happened to cause this issue, but it has been so long since I last tried to use FaceTime that any number of things could be in play.