Global Address List (GAL) search doesn't work.
Make sure you are configured in ActiveSync mode only. This error will occur if you are trying to connect in Exchange 2003 and/or Exchange 2007 mode instead of ActiveSync only. From the Settings screen Account tab, press the quick configuration button and follow the prompts, selecting ActiveSync ONLY on the protocols page.
To run Quick Configuration,