#Ruby on Rails チュートリアルの「1.4 Gitによるバージョン管理」でつまづいた
Bitbucketへの接続は問題ないし、SSHの認証鍵やプロジェクトを再作成しても
「git push -u origin --all」がうまくいかない...。

Bitbucketへのリポジトリ追加とリポジトリへのプッシュ

$ git remote add origin git@bitbucket.org:ユーザー名/hello_app.git
$ git push -u origin --all
To bitbucket.org:ユーザー名/hello_app.git
 ! [rejected]        master -> master (fetch first)
error: failed to push some refs to 'git@bitbucket.org:ユーザー名hello_app.git'
hint: Updates were rejected because the remote contains work that you do
hint: not have locally. This is usually caused by another repository pushing
hint: to the same ref. You may want to first integrate the remote changes
hint: (e.g., 'git pull ...') before pushing again.
hint: See the 'Note about fast-forwards' in 'git push --help' for details.

#結論
「-u」ではなく「-fu」を指定したところ解消

-fuへ変更

$ git push -fu origin --all