Sometimes there seems to be a race condition when authenticating against a computer account which was just created.
See this for more info:
I've seen this with multiple DC's. Although even in this case we've forced adcli to use a single DC. It may be that the presence of multiple DC's makes updating a computer account take longer?
Pushed to adcli master, is in adcli 0.7.1