The creation of the linked server does not fail. I copied the exact line of code and ran it separately on a SQL 2012 machine to create the linked server for a test and that succeeded. It just doesn't like it in the procedure in 2012. The same procedure has been running in SQL 2005 for years.

The error I get is:

Msg 7202, Level 11, State 2, Procedure ,<my procedure>, Line 49

Could not find server 'MyLinkedServer' in sys.servers. Verify that the correct server name was specified. If necessary, execute the stored procedure sp_addlinkedserver to add the server to sys.servers.

I'll add that if I create the linked server first and execute the procedure it does allow me to execute and I get the expected error that I explicitly raise telling me that the linked server already exists.