git push fails on new repos with fatal: authentication failed

Steps to reproduce:

1. Create a new git repo on bitbucket
2. Attempt to push code to it for the first time without cloning it

This fails with the error "fatal: authentication failed" even though I'm pretty sure I'm using the correct password. Following the same steps on github does not produce this error and works as expected, so I'm assuming it is a bitbucket issue.