Problem with searching by uid

[Kris Vassallo <kris@linuxcertified.com>]

I am experiencing a problem  where I am not able to search through my
database using the uid attribute. I am using the ldapsearch program and
doing the following (listing what works first and what doesn't work
second):

> ldapsearch -xb "dc=berkeley-da,dc=com" "(sn=vassallo)"   <--- This
works and will return the record below

# kris, People, berkeley-da.com
dn: uid=kris,ou=People,dc=berkeley-da,dc=com
sn: Vassallo
loginShell: /bin/bash
userPassword:: e2NyeXB0fSQxJFZsbkcxV3ZvJFFLMllCxxxxxxk3cU82U1VyUXZwMC8=
gidNumber: 506
uidNumber: 506
mail: Kris.Vassallo@berkeley-da.com
shadowMax: 99999
objectClass: inetOrgPerson
objectClass: posixAccount
objectClass: top
objectClass: shadowAccount
uid: kris
gecos: Kris Vassallo
shadowLastChange: 12660
cn: Kris Vassallo
homeDirectory: /home/kris
shadowWarning: 7


> ldapsearch -xb "dc=berkeley-da,dc=com" "(uid=kris)"        <--- This
doesn't work and returns to me the following

# extended LDIF
#
# LDAPv3
# base <dc=berkeley-da,dc=com> with scope sub
# filter: (uid=kris)
# requesting: ALL
#
# search result
search: 2
result: 0 Success
# numResponses: 1

Does anyone know why this is the case and what I can do to resolve this?
Thanks, 
Kris