SSH ключи для GitHub работают на BitBucket?
Может вы на битбакет по http пуши делаете?
Может, просто забыли, когда на битбакет тот же самый ключ добавили? В настройках аккаунта битбакета есть добавленный ключ? С какой сигнатурой?