there are loads of reasons this can happen….

from not having the correct certificate on iis on your front end server

to the galcontacts.db not downloading and generating correctly

being impatient waiting for the address book process to scan AD and process the enteries

but those most interesting one i have seen lately is the CRL checking feature and if a client machine cant do a crl check then the address book can fail…

there is a setting in IE you can turn this off on but its just another addition to the list of troubleshooting!