The SQL Server Native Client (SQLNCLI11) that ships with SQL Server 2012 does not support connections to SQL Server 2000 an earlier. I found this out during testing of our upgrade to SQL 2012. We upgraded our 2008 R2 servers in-place and it appears to have left the SQLNCLI10 provider in place but if you did a fresh install of SQL Server 2012 on a new server you may not have this provider. Does your 2012 server have the SQLOLEDB provider listed under Linked Server Providers in SSMS? If so, you could try using that.