This happens when the master on github is not a direct ancestor of the commit you are pushing. Most likely you made another commit in github without doing a pull back to stash git. updating the readme is a common way this happens.
I have not been able to figure out why dulwich breaks here, while regular git does not...
You have a few options:
1) Try git fetch followed by git merge follwed by git commit and push. This may or may not work, i have had mixed success, but ideally is the way to ensure you don't lose any commits.
2) Try git fetch then git branch newbranchname origin/master then git reset newbranchname --soft then git commit then push. Effectively this creates a new branch starting at the github master. Then, the reset sets HEAD to point at the new branch, but does not actually change any files, or the "index". Then commit recommits the index into the new branch (you lose your commit history, sort of like doing a rebase). finally you push it. note you will lose any commits that you had made directly to github but not merged locally, though those commits are available in remotes/origin/master, so you can use reset to reset individual files, etc.
3) clone the repo again to a new folder, copy the changed files from your old folder, then commit, push. just be sure you remember which folder is which, and delete the old one once you are sure everything took.
4) git remote sshorigin ssh://git@github.com/username/repo.git, then set up ssh keys using ssh_keygen, and going to github and pasting in the public key. This lets you git push sshorigin, which for whatever reason does not suffer from the problem of wanting only fast forward changes. Note you will lose whatever commits you made on github that were not merged into your local copy.