Yes, I wanted to post above what the fix was in case anybody else runs into this.

If you're going from 2012 SP1 to 2005 SP3 (probably from 2012 of any flavor to 2005 of any flavor) and get a collation conflict that you are sure isn't there (because you have inspected everything from point a to point z).

Try deleting the linked server and recreating it. Try each of the most common connection libraries as well.