Cannot obtain the schema rowset "DBSCHEMA_TABLES_INFO" for OLE DB provider "SQLNCLI" for linked server "FOO". The provider supports the interface, but returns a failure code when it is used.
and found the solution here http://support.microsoft.com/kb/906954
A little package that should have been run when the service pack was updated, but it didn't. I noticed that this is an issue with SP3 and SP4... too bad they didn't catch it in SP3 for the SP4 update. (though to be fair, they may not have known the package wasn't executing on the SP until people caught it with 64bit Sql Server)
Oh well. Hopefully, this will fix the error.