Do your ad domain controllers synchronize or if they do, have they synchronized correctly? Sounds like credential rights on the domain controllers to me.
1. Have you tried using a domain admin service account? it seems like a privilege issue on your end.
2. Are you using the default search filter?