IIRC, the Oracle client install should have installed the Oracle command line utility 'sqlplus'. If the location of 'sqlplus' was entered into your %PATH% variable, you can open a DOS prompt and type 'sqlplus' without getting an error. Use it to connect to your Oracle database. This is an alternate way of testing your TNS names connectivity (other than TNSPing).

I wrote a blog post on how to create a linked server to Oracle using T-SQL, it may help. http://expressnetsolutions.com/sqldch/?p=89. Unfortunately, I glossed over the Oracle install and troubleshooting...but if you follow the steps in the T-SQL you may get it to work.

I've seen cases where both the 32 and 64 bit client needed installing. Install the 32 bit version, attempt to create your linked server...if it doesn't work go with the 64 bit version.

It was a few years ago so working with the Oracle TNS names is fuzzy. IIRC there should be a GUI based tool in your Start menu to help you create your TNSNames file.