I am trying to add a contact to Outlook. It won't save it. When I try to
save, I get a message: Problem with Messaging Interface. If this happens
again, restart Outlook.

I restarted outlook without saving, same thing happened again. What is
causing the error and how do I fix it?

I don't use outlook for email. Just for contacts and sync with my
blackberry (which I also don't use for email).