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.
SQL 2012 (Native Client 11.0) does not support SQL 2000 any more by default.
Type linked server name in the [Linked server] text box.
Select [Other data source] at [Server type] option.
Select [SQL Server Native Client 10.0] at [Provider] drop-down list.
Type [SQLSERVER] at [Product name] text box.
Type <SQL 2000 server name or ip address> at [Data source] text box.