I seem to have solved this now. There was an issue with our kerberos5 config file, I basically removed a couple of lines from it to make it look like the config in this post (obviously with 'mydomain.local' replaced with our actual domain). I then restarted the server and then re-joined it to the domain. And to be clear, I DIDN'T use the format DOMAIN\<username> to login, I literally just put in my username and it worked. If I did put the domain prefix in, it doesn't work.....