I have objects like this:
dn: cn=1_2_3_4.gatesgroup.hu,cn=1.2.3.4,cn=vlan11,cn=Machines,dc=gatesgroup,dc=hu
dhcpHWAddress: ethernet 00:00:00:ff:ff:ff
gatesTCClass: 1234
gatesLastModified: 1136299622
objectClass: top
objectClass: dhcpHost
objectClass: gatesMachine
dhcpStatements: fixed-address 1.2.3.4
gatesBandwidth: 2048
cn: 1_2_3_4.gatesgroup.hu

If I do a: ldapsearch -x -W -LLL -D uid=myuser,ou=Users,dc=gatesgroup,dc=hu "(&(objectclass=gatesmachine)(gatesbandwidth=*))"

Every record is properly returned.
But if I try this, i got no result:
[root@ldap ~]# ldapsearch -x -W -LLL -D uid=mark,ou=Users,dc=gatesgroup,dc=hu "(&(objectclass=gatesmachine)(gatesbandwidth=2048))"
Enter LDAP Password:
[root@ldap ~]#