OK. Couple of things here. Firstly, if you have set up your system as per the doco (which I am assuming) then you have created a Consumer Organisation. Consumer Organisations contain OWA only users - no Outlook client and therefore no GAL (as OWA doesn't use the GAL - uses AD for contact searching). So that is the first thing. The next thing is that consumer users have their MSExchQueryDN set to themselves (not the OU like for business users). This means consumer users will only ever see themselves in any directory - they will not see other users in the GAL. This is by design. So try again but use a Business Org/User.
More importantly, what is it your are trying to do? I am here going to assume that you are trying to create contacts in order to provide "Hosted Contacts" for customer OUs. Whilst this is bread and butter for an enterprise installation, there is a limitation with providing this in a hosted scenario - let me try and explain.
In hosted exchange, customers only get access to users and objects within the OU that they were created in. If you have Cust1 and Cust2 OUs, then if you create a contact in AD for Cust1, Cust2 will not be able to see it. The problem arises when both Cust1 and Cust2 want to create a contact that is for the same email address e.g. someone@popularperson.com. The first contact will probably create OK. But because the smtp email address for an object needs to be unique within and AD forest, trying to create the contact again in the second OU with the same SMTP address will fail. This is a limitation by design in AD - not Hosted Exchange. MS are aware - we just have to wait to see if the left and right hands can find an answer ;-)
This is probably more than you wanted to know, but if you are looking at hosted contacts for your hosted exchange deployment - I thought I would share this now so you were prepared later on.
HTH.....Let me know if I need to clarify.
Ben Fletcher
Hosting Product Engineer