Whether or not it's the right place to post the solution (because apparently the question should not have been posted here in the first place), people are still going to come here looking for the solution because search engines bring it up. So, I'm posting my solution here:

After searching high and low, I finally gave up and started playing with Outlook myself to solve this. Now that I've come up with a fix, I figure I'll try to save all of you some time and post it.

Now that I know the solution for me, let me predict something for you: The user has (or at least had, at one time) multiple PST files open at the same time. The problem stems from Outlook's confusion as to where to put the contacts that you add, as each PST file has its own Contacts folder.

For me, I was able to view all of the Contacts folders my Outlook was aware of by clicking Tools > Address Book, then (within the Address Book window) Tools > Options. For me, there were multiple (5) entries in the "Keep personal addresses in:" drop down box. You can view which Contacts folder belongs to which PST file by selecting each Contacts entry in the bottom "When sending mail..." list one by one, and clicking Properties. Once you find the right Contacts folder (the one that leads to the Local PST file currently in use), remember its position in the list, and then select the corresponding Contacts entry in the "Keep personal addresses in:" drop down box.

Just as a note, what was actually happening to me was the drop down box was set to a Contacts folder stored in a PST file that I do not access anymore, hence Outlook not being able to add contacts to it.

Hope this works for you. Good luck.

Rob