Openldap Configuration issues

For the last few days I've been desperately reading official/user made guides in order to properly configure my openldap to allow users to login to a project management webapp (namely Redmine). With that said, please let me share the basic setup of the environment i'm dealing with.

Webapplication(s):

Redmine, Phpldapadmin

LDAP:

Openldap

After the installation, i took the following steps to re-configure my ldap to reflect better the ldap being used in production (since this whole redmine + ldap isn't in production yet)

Stopped slapd service and removed the cn=config.ldif from /etc/ldap/slapd.d

Modified /usr/share/slapd/slapd.conf to this:

include         /etc/ldap/schema/core.schema
include         /etc/ldap/schema/cosine.schema
include         /etc/ldap/schema/nis.schema
include         /etc/ldap/schema/inetorgperson.schema

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

modulepath  /usr/lib/ldap
moduleload  back_mdb

sizelimit 500
tool-threads 1

backend     mdb
database        mdb
suffix          "o=testcompany.com"
rootdn          "cn=admin,o=testcompany.com"
directory       "/var/lib/tc-ldap"
rootpw          "password"

index           objectClass eq
index       uid eq
index       ou eq
index       default eq,sub

lastmod         on
checkpoint      512 30

access to attrs=userPassword,shadowLastChange
        by dn="cn=admin,o=testcompany.com" write
        by anonymous auth
        by self write
        by * none

access to dn.base="" by * read

access to *
        by dn="cn=admin,o=testcompany.com" write
        by * read

Afterwards, slaptest -f /usr/share/slapd/slapd.conf -F /etc/ldap/slapd.d which generated my new cn=config.ldif
Set the appropriate user/group to the new cn=config.ldif with chown -R openldap:openldap /etc/ldap/slapd.d/
Fired up slapd service and checked if the ldap was running or not. Since it was and i could access it with phpldapadmin, i added an organizationalUnit (ou=sales), all the country codes and imported 3000 users (by using ldapadd) Now my DIT looks as follows
```
- o=testcompany.com
  - ou=sales
    - AD
      + uid=123456,c=AD,ou=sales,o=testcompany.com
      + ...
```
which is great, this is exactly the way it should look like, however I've noticed, that cn=admin,o=testcompany.com entry doesn't exists, while it did using the default config after i've installed openldap.
In Redmine, I've configured and tested the ldap authentication. It is working correctly (it can both connect to my ldap and If i wish to add a new user and choose the before configured ldap authentication for it, i can even choose from the entries that are in my ldap, which is also great)
However (this is where my problem is) when i try to log into Redmine with a user that i've just created (with ldap authentication) i always get Invalid credentials error (while it works like a charm when i login with any other account, created with Simple Authentication)

These events led me to believe that the error is in the LDAP configuration. After a few more hours/days of fooling around with the ACLs and dpkg-reconfigure slapd (and even purging-reinstalling slapd and ldap-utils) i still can not get beyond this point. And one more bit of information, after dpkg-reconfigure slapd and creating a few users under the default dc=example,dc=com, i can get them to log into Redmine just fine (and even cn=admin,o=testcompany.com shows up...).

Below i'll attach a few things that I've tried. I hope someone can aid me with a few tips as to where i got off the trail (somehow i feel that i'm missing the obvious here).

What I have tried so far:

    1. modify the default slapd.conf file, and repeat the process i've written above
    2. create a completely new one 
    3. a lot of different ways to add/modify the ACL
    4. read through a lot of mailing list, similar problems on redmine forums, and openldap mailing lists, still no success (i can paste a lot of links from my .txt if you need it)