Thanks for the replies. Both of these are suggestions that I did not run in to when googling for an answer. I will try these and report back with what I find.
I talked to one of our sysadmins who mentioned that the SQL server service account was not set up for kerberos delegation so that might be playing a part in this.