What COM Add-In is it? I had a problem with the Personal Folders backup add-in, when you install it as the admin it only gets added to the admin mail profile and not the users.
To fix I logged into Outlook as the user, then: Tools>Options>Other>Advanced Options...>COM Add-ins...>Add...
Then browse to the exe/dll of the add-in you want (In my case c:\program files\microsoft office\office11\addins\outbak.dll) and that should add the functionality to their profile too.
Hope this helps,
Al