The problem is most likely Mail's inability to transverse an alias to a cloud storage or a syncing service.
Here's one method to fix that.
1) Quit Mail, as well as Contacts, Calendar, and Reminders, if they're open.
2) Use the Finder to navigate to ~/Library/Application Support. (The ~ represents the user's home folder.) You may notice that the Library folder doesn't seem to be present on your Mac. That's because it's been hidden since the introduction of OS X Lion.
3) Once you're in the Application Support folder, you'll notice that the AddressBook folder seems to be missing, too. You'll see an alias called AddressBook; you can tell it's an alias by the little arrow in the bottom left corner of the icon. If the AddressBook folder isn't an alias, stop right here. The problem you're having is probably related to something else.
4) If the folder is an alias, then you can continue.
5) The alias points to the AddressBook folder that you moved to your cloud service. In order to correct the Mail problem, you need to copy the AddressBook folder from your cloud service back to your Mac, and then delete the alias.
6) Open your cloud storage service. This will vary from service to service, but in most cases, there will be a folder on your Mac that shows all of the data you have stored in the cloud service. Open this folder and locate the AddressBook folder.
7) Leave this Finder window open; we will be dragging the AddressBook folder to your Mac in a later step.
8) In the Application Support folder on your Mac, delete the AddressBook alias by right-clicking the alias and selecting Move to Trash from the pop-up menu.
9) Leave the Application Support Finder window open as well.
10) With the alias gone, we can copy the actual AddressBook folder back to your Mac. From the Finder window that's open to your cloud service, drag the AddressBook folder to the Application Support folder on your Mac.
11) When the copying is complete, you can launch Mail. The Address Panel and the Auto-Complete function should both be working.
Please post back with results.
SM