I've managed to get it working again, but not sure if by coincidence, or if what I did actually fixed the problem.
All I did was deselect all preferred coturns for ICE in the list, and deselect force relay connection.
You can do this by ctrl-clicking any selected coturns. Alternatively, select all of them with shift-click.
I tested that it stopped working with a single prefered coturn, and worked again by doing the above.
This seems backwards because these are the initial troubleshooting steps to take when not connecting in the first place, but this is what worked, so there you go.
Hopefully it works for you too.

I'm having the same problem with almost the exact same circumstances.

I too have started playing online for the first time in almost 12 months.
I had 1 good 1v1 game (although a bit laggy), since then every matchmaking game has failed because I couldn't connect. I tried joining a custom lobby and only connected to 2 out of 8 players, one of which was the host.
I've tried forcing relay connection and preferred coturns for ICE, and disabling ipv6, with nothing working.

My ISP is TPG (no CG-NAT) in NT, Australia, and my connection has been otherwise stable.