If your issue is with linked servers, you need to look at a few things.
First, your users need to have delegation enabled and if the only thing that’s changed, it’l likely they do. Otherwise you can uncheck the “Account is sensitive and cannot be delegated” checkbox is the user properties in AD.
Second, your service account(s) must be trusted for delegation. Since you recently changed your service account I suspect this is the culprit. (http://technet.microsoft.com/en-us/library/cc739474(v=ws.10).aspx)
You mentioned that you might have some SPN issues, so be sure to set the SPN for both endpoints, otherwise you will not be able to see the delegation tab in AD. Also make sure you’re in advanced view in “Active Directory Users and Computers.”
If you still do not see the delegation tab, even after correcting your SPN, make sure your domain not in 2000 mode. If it is, you can “raise domain function level.”
At this point, you can now mark the account as trusted for delegation:
In the details pane, right-click the user you want to be trusted for
delegation, and click Properties.Click the Delegation tab, select the Account is trusted for delegation
check box, and then click OK.
Finally you will also need to set all the machines as trusted for delegation.
Once you’ve done this, reconnect to your sql server and test your liked servers. They should work.