Can you please verify that the version of your Oracle client matches that of your database? You say that you have an Oracle 11g database, but you need to first make sure that your client is of the same of later version. If your database is 11g R2 (as an example, 11.2.0.2) but your client is 11g R1 (as an example, 11.1.0.9) or 10g (as an example, 10.2.0.1) then you could run into issues. Also, have you installed the full version (administrator) of the client or a different version?
If the above doesn't help, then refer to the following...
Which versions of ArcGIS Server and ArcSDE are you using?
Is SDEHOME correctly defined in the environment variables? (From command prompt, type echo %SDEHOME%)
For the SDE connection file you're using to register your enterprise GDB as a data store, does it use an ArcSDE application service or does it use EZCONNECT? (If EZCONNECT, is your Oracle instance configured for EZCONNECT?)