Just wondering, if you try to add a user does the GAL show there? If not re-create the MAPI profiles.
You could create the profile again anyways to rule that out.
Use this article for the profile re-creation: BlackBerry Search Results
If this don't do it then I'm not sure. Might have to get a better thinking cap, like Think-O-Matic 9000