There is a long-standing bug in (Open)Solaris and derivatives (including NexentaStor) that breaks Active Directory interoperability:

Beginning with Windows Server 2003, Active Directory supports VLV searches. Every VLV search request must be accompanied by 2 request controls: the SSS control and the VLV control. However, Active Directory imposes some general criteria on the SSS control:

1. Cannot sort based on more than one sort keys/attributes.
2. Cannot sort based on the “distinguishedName” attribute (presumably Microsoft does not use the “DN” attribute).
3. Cannot sort based on a constructed attribute (presumably an attribute not stored on Active Directory).

Unfortunately, Solaris LDAP clients use 2 sort keys/attributes: “cn” and “uid” in the SSS control. Subsequently, when dumping a container or a naming database, Solaris LDAP clients would receive LDAP_UNAVAILABLE_CRITICAL_EXTENSION.

$ ldaplist passwd
ldaplist: Object not found (LDAP ERROR (12): Unavailable critical extension.)

This issue has been detailed elsewhere, including at utexas.edu. There appear to be at least four solutions:

1. Wait for the fix from Sun Oracle to reach the light of day: this bug was apparently fixed in SNV 144. (I expect the fix is out in Solaris 11 Express now, but have not tested this myself.)
2. Apply the hotfix in Microsoft’s KB886683 to your domain controllers, which will disable VLV.
3. Run separate ADAM instances with VLV disabled, and point your Solaris machines at them instead of directly at your domain controllers. From the blog post linked above, it sounds like the University of Texas chose this route.
4. Use OpenLDAP as a proxy in front of Active Directory; configure your Solaris machines to use the proxies instead of Active Directory servers. This is the solution detailed in this blog post.

Method
I tested on Ubuntu 10.04 here, although adaptation for your chosen OS is probably straightforward.

First, build OpenLDAP; we need several options not included in the default .deb, so we’ll do this from source, with the following “configure” options:

./configure --prefix=/opt/openldap --enable-meta --enable-ldap --enable-rewrite 
--enable-rwm

(You will probably also want to take the extra step of building a package for your OS, to ease configuration management.)

After installing OpenLDAP, edit slapd.conf to proxy to your domain controllers. In this example, we’re pointing the proxies at some older Windows 2003 hosts using the Microsoft Services for Unix (SFU) extensions, so we’ll take this opportunity to make make what Solaris sees closer to RFC 2307-compliant and eliminate the need for attributeMap arguments to ldapclient on the Solaris host:

#
# See slapd.conf(5) for details on configuration options.
# This file should NOT be world readable.
#
include  /opt/openldap/etc/openldap/schema/core.schema
include  /opt/openldap/etc/openldap/schema/cosine.schema
include  /opt/openldap/etc/openldap/schema/inetorgperson.schema
include  /opt/openldap/etc/openldap/schema/nis.schema
include  /opt/openldap/etc/openldap/schema/mssfu30.schema

# Time out connections before the proxied bind drops:
idletimeout 60

pidfile  /var/run/slapd/slapd.pid
argsfile /var/run/slapd/slapd.args

access to dn.base="" by * read
access to dn.base="cn=Subschema" by * read
access to *
 by self write
 by users read
 by anonymous auth

loglevel   256

######################################################
# database definitions
######################################################

database ldap
suffix  "dc=example,dc=com"
uri  "ldap://dc1.example.com ldap://dc2.example.com"
acl-bind bindmethod=simple binddn="cn=ldapproxy,ou=Service Accounts,ou=Users,dc=example,dc=com" credentials=secret

# Do mapping in OpenLDAP, instead of on client, eliminating need for
# AD schema attribute mapping:
overlay rwm
rwm-map attribute       userpassword    msSFU30Password
rwm-map attribute       memberuid       msSFU30MemberUid
rwm-map attribute       gidnumber       msSFU30GidNumber
rwm-map attribute       gecos           name
rwm-map attribute       uid             msSFU30Name
rwm-map attribute       uidnumber       msSFU30UidNumber
rwm-map attribute       homedirectory   msSFU30HomeDirectory
rwm-map attribute       loginshell      msSFU30LoginShell
rwm-map objectclass     posixGroup      group
rwm-map objectclass     posixAccount    user

Walking through this config file line-by-line, not the following (keyed by line number):

3. Make the file owned by user “root”/group “openldap” without “other” read permissions (assuming you’ll be running OpenLDAP as user “openldap” in group “openldap” – adapt as necessary for your site), e.g.:

-r--r----- 1 root openldap 1569 2010-08-04 14:51 slapd.conf

9. We need to add some schema information for the older Microsoft Services for Unix extensions; they’re available in a GitHub Gist.

30-33. Configure the connection to the Active Directory servers. Note in particular that the database type is “ldap” meaning that another LDAP server (AD) is used as the data source, via a proxy. Line 33 is a user in Active Directory to which you bind to the back-end servers as.

37-47. Map the SFU attributes to their RFC 2307 equivalents. Note that you will need to populate msSFU30MemberUid manually – here’s one way to do it.

Other than that, perhaps an init script and a file for /etc/default/slapd (both lightly adapted from the stock Ubuntu “slapd” .deb), and you should be good to go.

References: eldapo: openldap as a pass-through proxy