I had it on Windows and it stopped working yesterday and thougth the DB is corrupt and rebuilt it and same issue. If I change to Plex Movie (legacy) or The movie database it works.
I try match manually and this is what I get.
You were right. It was DNS. I noticed that for some reason metadata-static.plex.tv is being blocked on my DNS. I turned it off for testing and it worked. I turned it on yesterday and new shows etc had no metadata and the match stopped working. I’ve removed this rule now (no idea how it was added in the first place) and restarting Plex and I can match works ASAP.