It turns out it was a "double hop" issue and Windows Credential Guard on the user's computer was blocking the second hop. Credential Guard is enabled by default on some new windows 11 installations. This explains why the Domain Admin was getting the error on his windows 11 machine. When we disabled Credential Guard on the problematic user's computer, everything worked as expected.