Make sure your refs for pushing are correct. This tutorial is pretty great, right from the documentation:
http://wiki.eclipse.org/EGit/User_Guide#GitHub_Tutorial
You can clone directly from GitHub, you choose where you clone that repository. And when you import that repository to Eclipse, you choose what refspec to push into upstream.
Click on the Git Repository workspace view, and make sure your remote refs are valid. Make sure you are pointing to the right local branch and pushing to the correct remote branch.