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