When adding the user the global address list needs to initialize. There maybe an issue with the mapi profile.
you can go into the registry to:
hkcu/software/microsoft/windows nt/current version/windows messaging subsystem/profiles and delete the BlackBerryManager profile.
***always backup the registry before making changes
when you reopen the manager it should prompt for a new profile, make sure you hit checkname to ensure it resolves correctly then try again.
I received the Mailstore Adaptor DLL initialisation error too when trying to add a new user in BlackBerry Manager 4.1. My resolution to this was to re-install Lotus Notes. Works fine now.