internal -x -b "dc=company,dc=internal" -D "cn=ldap proxy,cn=Users,dc=company,dc=internal" -w 'passwd' -LLL "(sAMAccountName=testuser)"

My slapd.conf looks like:
slapd.conf
-----------
include         /etc/openldap/schema/core.schema
include         /etc/openldap/schema/cosine.schema
include         /etc/openldap/schema/inetorgperson.schema
include         /etc/openldap/schema/nis.schema

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

loglevel 1024

database    ldap
suffix    "cn=Users,dc=company,dc=internal"
rootdn   "cn=ldap proxy"
uri   "ldap://charizard.company.internal"

binddn     "cn=ldap proxy,cn=Users,dc=company,dc=internal"
bindpw     "passwd"

rwm-rewriteEngine on
rwm-map objectclass account user
rwm-map attribute uid sAMAccountname
rwm-map attribute cn name
rwm-map attribute sn sn
rwm-map attribute mail    userPrincipalName
rwm-map attribute *

lastmod    off
chase-referrals no

access to * by * read

-----------------------------

When I try and search on my openldap host, I recive..

[kylec@localhost ~]$ ldapsearch -v -H ldap://localhost -x -b "cn=Users,dc=company,dc=internal"
ldap_initialize( ldap://localhost )
filter: (objectclass=*)
requesting: All userApplication attributes
# extended LDIF
#
# LDAPv3
# base <cn=Users,dc=company,dc=internal> with scope subtree
# filter: (objectclass=*)
# requesting: ALL
#

# search result
search: 2
result: 1 Operations error
text: 00000000: LdapErr: DSID-0C090627, comment: In order to perform this ope
ration a successful bind must be completed on the connection., data 0, vece

# numResponses: 1

--------------------------------

In slapd debug log I can see the following...

backend_startup_one: starting "cn=Users,dc=corpedia,dc=internal"
ldap_back_db_open: URI=ldap://charizard.corpedia.internal
slapd starting
ldap_pvt_gethostbyname_a: host=heracross.corpedia.local, r=0
connection_get(9): got connid=0
connection_read(9): checking for input on id=0
ber_get_next
ber_get_next: tag 0x30 len 12 contents:
ber_get_next
ber_get_next on fd 9 failed errno=11 (Resource temporarily unavailable)
do_bind
ber_scanf fmt ({imt) ber:
ber_scanf fmt (m}) ber:
>>> dnPrettyNormal: <>
<<< dnPrettyNormal: <>, <>
do_bind: version=3 dn="" method=128
send_ldap_result: conn=0 op=0 p=3
send_ldap_response: msgid=1 tag=97 err=0
ber_flush: 14 bytes to sd 9
do_bind: v3 anonymous bind
connection_get(9): got connid=0
connection_read(9): checking for input on id=0
ber_get_next
ber_get_next: tag 0x30 len 69 contents:
ber_get_next
ber_get_next on fd 9 failed errno=11 (Resource temporarily unavailable)
do_search
ber_scanf fmt ({miiiib) ber:
>>> dnPrettyNormal: <cn=Users,dc=corpedia,dc=internal>
<<< dnPrettyNormal: <cn=Users,dc=corpedia,dc=internal>, <cn=users,dc=corpedia,dc=internal>
ber_scanf fmt (m) ber:
ber_scanf fmt ({M}}) ber:
==> limits_get: conn=0 op=1 dn="[anonymous]"
ldap_create
ldap_url_parse_ext(ldap://charizard.corpedia.internal)
=>ldap_back_getconn: conn 0x8ad8a88 inserted refcnt=1 binding=1
ldap_search_ext
put_filter: "(objectClass=*)"
put_filter: simple
put_simple_filter: "objectClass=*"
ldap_send_initial_request
ldap_new_connection 1 1 0
ldap_int_open_connection
ldap_connect_to_host: TCP charizard.corpedia.internal:389
ldap_new_socket: 10
ldap_prepare_socket: 10
ldap_connect_to_host: Trying 10.0.0.6:389
ldap_connect_timeout: fd: 10 tm: -1 async: 0
ldap_open_defconn: successful
ldap_send_server_request
ber_scanf fmt ({it) ber:
ber_scanf fmt ({) ber:
ber_flush: 73 bytes to sd 10
ldap_result ld 0x8ad0860 msgid 1
ldap_chkResponseList ld 0x8ad0860 msgid 1 all 0
ldap_chkResponseList returns ld 0x8ad0860 NULL
wait4msg ld 0x8ad0860 msgid 1 (timeout 100000 usec)
wait4msg continue ld 0x8ad0860 msgid 1 all 0
** ld 0x8ad0860 Connections:
* host: charizard.corpedia.internal port: 389 (default)
refcnt: 2 status: Connected
last used: Fri Mar 27 16:23:13 2009

** ld 0x8ad0860 Outstanding Requests:
* msgid 1, origid 1, status InProgress
   outstanding referrals 0, parent count 0
** ld 0x8ad0860 Response Queue:
   Empty
ldap_chkResponseList ld 0x8ad0860 msgid 1 all 0
ldap_chkResponseList returns ld 0x8ad0860 NULL
ldap_int_select
read1msg: ld 0x8ad0860 msgid 1 all 0
ber_get_next
ber_get_next: tag 0x30 len 167 contents:
read1msg: ld 0x8ad0860 msgid 1 message type search-result
ber_scanf fmt ({eaa) ber:
read1msg: ld 0x8ad0860 0 new referrals
read1msg: mark request completed, ld 0x8ad0860 msgid 1
request done: ld 0x8ad0860 msgid 1
res_errno: 0, res_error: <>, res_matched: <>
ldap_free_request (origid 1, msgid 1)
ldap_free_connection 0 1
ldap_free_connection: refcnt 1
ldap_parse_result
ber_scanf fmt ({iaa) ber:
ber_scanf fmt (}) ber:
ldap_msgfree
send_ldap_result: conn=0 op=1 p=3
send_ldap_response: msgid=2 tag=101 err=1
ber_flush: 163 bytes to sd 9
connection_get(9): got connid=0
connection_read(9): checking for input on id=0
ber_get_next
ber_get_next: tag 0x30 len 5 contents:
ber_get_next
ber_get_next on fd 9 failed errno=0 (Success)
connection_read(9): input error=-2 id=0, closing.
connection_closing: readying conn=0 sd=9 for close
do_unbind
connection_close: deferring conn=0 sd=9
connection_resched: attempting closing conn=0 sd=9
connection_close: conn=0 sd=9
=>ldap_back_conn_destroy: fetching conn 0
connection_get(9): connection not used
connection_read(9): no connection!

Any help would be much appreciated :-)