Git push failed, "Non-fast forward updates were rejected"

Add --force to your command line if you are sure you want to push. E.g. use git push origin --force (I recommend the command line as you will find much more support from other users with the command line. Also this may not be possible with SmartGit.) See this site for more information: http://help.github.com/remotes/

Pull changes first:

git pull origin branch_name

Before pushing, do a git pull with rebase option. This will get the changes that you made online (in your origin) and apply them locally, then add your local changes on top of it.

git pull --rebase

Now, you can push to remote

git push 

For more information take a look at Git rebase explained and Chapter 3.6 Git Branching - Rebasing.