Not knowing exacly how you're setup here's my first guess: Right click on the Contacts icon, Properties, Outlook Address Book tab, make sure 'Show this folder as an Outlook Address book' is checked.
If that's not it, your answer is in Tools, Services. But I can't give specifice without knowing what version of Outlook you've got or what services you have enabled.