A Mercurial repository gets its identity when you make the first commit in it. When you create a new repository on Bitbucket, you create an empty repository with no identity.
When you clone this repository to machine A and make a commit and push it back, then you brand the repository. If you have cloned the repository on the second machine before pushing from the first, then you can end up in the situation you describe.
Please run hg paths on the machine where you cannot push. Then make a separate clone of the repository it says it will push to. Now examine the first changeset in each repository with
hg log -r 0
If the initial changesets are different, then you have two unrelated repositories, as we call it in Mercurial. You can then export the changes you cannot push as patches and import them in the other.