How do I clean up my Github fork so I can make clean pull requests?

I forked a repository on Github. I've made some minor changes and submitted pull requests to the upstream, but along the way my fork has become so mangled I'm unable to generate clean pull requests; when I start a pull request from a branch with six changes, Github wants to submit thirteen, with seven of them already existing upstream (natch).

My problem seems to be related to only pulling the latest commits, but when I create a new branch and cherry-pick commits I still have extras. I've futzed with rebasing as well, but now it looks like even my master is so messed up I can't generate a clean copy of upstream. This is apparently because I didn't understand that I needed to rebase instead of merging, so clearly I've made mistakes; what I'm trying to do is figure out how to unsnarl that knot and get back to a clean state where I can move forward usefully.

I kind of want to blow away my fork and make a new fork of the upstream, but I gather that, too, is difficult.

Having confessed my Git sins, how do I obtain github absolution?

Step 1: Pull upstream changes
It's recommended to add the upstream repo as "upstream" as explained on the Fork a Repo page:

git pull --rebase upstream master

The --rebase option places your changes on top of the latest commit without merges.

Step 2: (Optional) Merge your commits into 1 commit

git reset --soft upstream/master

This command will "undo" all your commits, but won't change the files. So you can commit all your changes in a single commit.

git commit -a

Step 3: Check & test your changes

To show the changes use a GUI like the built-in gitk, Sourcetree, TortoiseGit or Tower (paid), etc.

Step 4: Push

git push will throw an error, because the push would change the target repository's history.
If you're confident the changes shown in step 3 are correct then push with "-f"

git push -f origin master

Additional information
The command to add a remote is:

git remote add upstream git://github.com/[username]/[project].git

You can also also pull from a direct URL:

git pull --rebase  git://github.com/[username]/[project].git

But then you'll need the hash of the latest upstream commit instead of "upstream/master" in the other steps.

As I understand it, with both Git and Mercurial (I've only used the latter, so I may be wrong) it isn't a big deal at all to blow away a fork and re-fork it. I do that all the time with my projects. If you're ok with doing that (can back up your changes, or don't have any significant changes in your fork), I'd say that's probably the way to go.

Remember, with DVCS, forking a repository makes a full clone of that entire repo. If you delete your current fork and then fork the original repo again, you'll have a completely clean slate to work from.

On your private repo, add the forkee's repo as a remote. Rebase/reset your branches from the remote's branches. Do a force push to your github repo.

If you need exact commands, let me know. Also let me know whether you want to try and preserve local commits or if "blowing away" is OK.