If you have more than one AD DC, make sure they actually synchronized.
If there is only one, it might well be that a credentials manager has a
cached version of the key for the MS SQL account.

We have a winner! To close the loop with anyone who runs into this issue in the internets... The SPN needs to be on the same service account used to run SQL Server (which seems obvious now that its working). My SQL Server was running as a local account not a domain account. Switching it over to the same account that had the spn fixed it immediately.

Thanks again for your help.

Marc