Make sure the Outlook Address Book service is in the user's profile. Check
the Mail applet in the Control Panel. If the Outlook Address Book service
isn't on the list of addable services try this:

Add the following to your C:\WINDOWS\SYSTEM\MAPISVC.INF file (Oh, make a
copy before you try this, just in case)

In the [Services] section at the top of the file add this to the list:

CONTAB=Outlook Address Book

At the bottom of the file add these sections:

[CONTAB]
Providers=CONTABP
PR_SERVICE_DLL_NAME=contab.dll
PR_SERVICE_SUPPORT_FILES=contab.dll
PR_SERVICE_DELETE_FILES=contab.dll
PR_SERVICE_ENTRY_NAME=ServiceEntry
PR_RESOURCE_FLAGS=SERVICE_NO_PRIMARY_IDENTITY | SERVICE_SINGLE_COPY

[CONTABP]
PR_PROVIDER_DLL_NAME=contab.dll
PR_RESOURCE_TYPE=MAPI_AB_PROVIDER
PR_PROVIDER_DISPLAY=Outlook Address Book
PR_RESOURCE_METHODS=STATUS_SETTINGS_DIALOG

Try to add the service after you save the file.