I have been working with a client on upgrading their PeopleSoft database from SQL Server 2000 to 2012.  Everything has gone great, except when we tried to setup a Linked Server back to their other SQL Server 2000 databases.  SQL Server 2012 uses the SQLNCLI-11 Native Client which has backwards compatibility for two release levels, so SQL Server 2008 and 2005 are supported by this client.  You can use the SQL Server 2008 Native Client SQLNCLI-10 which does support backwards compatibility to SQL Server 2005 and 2000.

When setting up the linked server using the SQLNCI-10 Native Client, it was failing with an odd error:

The stored procedure required to complete this operation could not be found on the server. Please contact your system administrator.

After a looking around I found this knowledge base document 906954 which explains that because of the SQL Server 2012 environment running on x64 and the SQL Server 2000 environment is running on x86 that there are some compatibility issues that require the SQL Server 2000 environment needs to be at SP3 or SP4 patch level.  PeopleSoft certification documents show that their support requires the SQL Server 2000 database to be at SP3a, and they do support SP4.