Similar problem with SQL 2005 x64 and Oracle 11g client library. Second error message is:

"Cannot get the column information from OLE DB provider "OraOLEDB.Oracle" for linked server "x".

And, oddly, I get an empty result set with the column headings displayed, so the column information error message seems a little uncertain.

I can connect to the Oracle server using the Oracle Provider for OLE DB in a Data Link UDL file, but that could be 32-bit. But in either case it isn't MSADORA, which was working on SQL 2000 32.