When doing a join against a domain with more than one DC, need to make sure the same KDC's and/or LDAP servers being used. This is because accounts are being created, used, before there's time for replication.
Related to, and more details at bug #861366
adcli-0.4-1.fc18 has been submitted as an update for Fedora 18. https://admin.fedoraproject.org/updates/adcli-0.4-1.fc18
Package adcli-0.4-1.fc18: * should fix your issue, * was pushed to the Fedora 18 testing repository, * should be available at your local mirror within two days. Update it with: # su -c 'yum update --enablerepo=updates-testing adcli-0.4-1.fc18' as soon as you are able to. Please go to the following url: https://admin.fedoraproject.org/updates/FEDORA-2012-18051/adcli-0.4-1.fc18 then log in and leave karma (feedback).
adcli-0.4-1.fc18 has been pushed to the Fedora 18 stable repository. If problems still persist, please make note of it in this bug report.