Seems that this might be the solution... http://stackoverflow.com/questions/3057257/ubuntu-10-04-lucid-openldap-inval...
Actually, it seems that that wasn't the solution...
So when I run:
ldapsearch -x -H ldap://127.0.0.1 -b 'cn=config' -D 'cn=config' -s base -LLL -W olcLoglevel
I get: Enter LDAP Password: ldap_bind: Invalid credentials (49)
Funny thing is, I never had any problems configuring ldap until I switched to Ubuntu.