I just managed to work around the problem by disabling the plugin "Exchange Operations" under "Edit" -> "Plugins". Now I can add address book again; strange... -- Can't add new address book https://launchpad.net/bugs/39086