Kerberos was giving the wonderful error: "Server's entry in database has expired" when you tried to get a ticket. Sometimes this is caused by the date/time on servers going squiff. This time it wasn't. Since my Google foo failed me and a member of the MIT Kerberos team saved me a lot of digging I thought I'd put this out on the interwebs.
The actual error code gives slightly more of a hint "KRB5KDC_ERR_SERVICE_EXP"
The message was referring to the Ticket Granting Service principal having expired ie. krbtgt/REALM@REALM (eg krbtgt/EXAMPLE.COM@EXAMPLE.COM)
It would appear that one of my colleagues (who apparently at this point can retire whenever he wants) didn't expect to still be here when he initially set up the service... Remove the expiry and hey presto everything works again, just like magic.
Having just fired up wireshark when tlyu gave me the answer and then not closed it when I left. I'm amused to see that I might not have been quite as far from finding the answer as I thought... Just below the line I'd started to examine
Server Name (Unknown) : krbtgt/OURREALM