So, as it turns out, this was caused by our service not being configured with a SPN (Service Principal Name). This can be done using the setspn tool with Windows Server. (See this MSDN article for more information.)
Once the SPN was applied, Kerberos authentication started to work as expected.