Right, your LDAP credentials may be fine. But SQL Server isn't connecting to the OID Linked Server using LDAP. I know the provider you're using should technically be LDAP b/c that's what AD uses also but I wouldn't trust MS LDAP and Oracle LDAP to speak to each other easily.

I know it mentions SQL 2005, but have you tried something like this: MSDN.

Edited for clarity.