There are a couple of reasons why Address AutoComplete may not work.
Note: Address Autocomplete does not work for Safari, Opera, and non-JavaScript enabled browsers.
A few things to check:
Supported Browsers:
Remember, even if you can’t AutoComplete addresses, you can still insert contacts from your Address Book by clicking on the "Insert addresses" or "To:" links on your Compose page.