rehosting to a new remote without access to old one

[Jeffrey_Cunningham]

I lost my connection with my previous remote host for a git project - it's gone forever. I have a local copy of of the project - with history - I would like to host on Bitbucket. I created a new project but can't figure out how to push my project up to it. I tried:
git remote add origin git@bitbucket.org:myaccount/myproject.git
git push -u origin master

and

git push --all new-origin

But I always get the following:

error: refs/heads/dev does not point to a valid object!
error: refs/heads/master does not point to a valid object!
error: refs/heads/signalset does not point to a valid object!
<snip>
fatal: The remote end hung up unexpectedly

Any idea how to do this?

[Jeffrey_Cunningham]

I should have mentioned that I know how to push it up there without history (clone the new project, copy the files, add and commit them, and push it). It's a long detailed history that needs to be saved.