Check that the service can access the registry entry with tells oracle where the tnsnames.ora file is located. From memory it is HKLM\SOFTWARE\ORACLE\Key_Client with a TNS_NAMES registry string which is the folder holding the tnsnames.ora file. You can also create the same thing in the HKCU tree.
Oops ! now i'm at work i can see the string name should be TNS_ADMIN. Also try the env variable TNS_ADMIN and make sure there is nothing in HKCU.
Noticed as well you need the sqlnet.ora file in the same folder as tnsnames.ora