It turns out we had another 16.04 machine which was working fine. But as
soon as I updated its sudo from 1.8.16-0ubuntu1.2 to 1.8.16-0ubuntu1.3,
it stopped working too.
So it looks like I have a reproducing case for this and I can
investigate further - I suspect it's a behaviour change from this fix:
Manage your subscription for the Freeipa-users mailing list:
Go to http://freeipa.org for more info on the project