1) Have you installed the oracle client on the server?

2) Have you rebooted the server afterwards?

3) Can you connect to the linked server by using the Oracle Tools on the server? (tnsping, ...) (not using sql server)

Current linked server settings (out of my head, will correct it tomorrow)

*note tables in ORACLE are in UPPERCASE*

*selecting from oracle through sql : linkedservername..SCHEMA.TABLENAM*

Linked server name myOracle

Provider name= Microsoft OLEDB for Oracle

Product name= Oracle

Datasource = myOracleServer.world

*edit*

This article discusses how to setup an Oracle Linked server

http://www.databasejournal.com/features/mssql/article.php/3290801