Seems that a small change (http -> https) in the captive portal detection configuration file broke it.
If we want captive portal detection (I think we do), this should probably be fixed. Otherwise, we should remove NetworkManager-config-connectivity-fedora from our default install.