Apparently you first need to wait for the address to be confirmed after attaching it to the tangle. The transaction went through with another address that was confirmed.