If you want them to add users to the local machine while logged onto the network you have to add there Domain Users account, don't create a new account for them on the local account. Put that Domain User account under Administrators group in the Local Machine and that should fix it, thus whenever they log on there machine to the Domain they will still have Administrative Priveledges on the Local Machine. If you added them to the local machine by creating a new username and password then it won't work unless they are logged locally.
Hope that helps, let us know