Turns out that it needed the -Credential flag, which Microsoft doesn't document as a requirement. This worked find...

Add-Computer -DomainName "mydomain" -Credential mydomain\myusername