Thanks guys,

I used the wizard to configure my GAL. I entered a account under with administrator privileges for the DN : The AD authentication worked without hassles. You guys really did a great work.
After the initial configuration of the GAL it returned no search results so I viewed a thread on the AD configuration, run the command:
root@zmail:~# /opt/zimbra/bin/zmprov sg pinochio
It returned the query results from AD, that confirmed that it can actually query and it has the necessary permission.
I then logged in as a user with an account created on AD, tried the GAL, and it worked!
Don't ask me what happened!