This does sound odd, and the message may be misleading. Can you create users in other organisations in the same deployment ?
If not, the issue could be either with SQL permissions in the MSCRM_Config database, or with permissions in AD, though I would expect either would show a more useful message
Otherwsie, if it is specific to one organisation in the deployment, you might want to check the permissions on the business units
Microsoft CRM MVP - http://mscrmuk.blogspot.com/ http://www.excitation.co.uk