Git: Cannot rebase because of uncommitted changes

Probably not yet for a golden shovel, nevertheless I always use --autostash option when rebasing with uncommitted changes, thus:

git rebase --interactive SHA_WHERE_REBASE_ONTO^ --autostash

git stash stores the different files away from everything else, returning your working directory to the last commit. Once you have done your rebase, run git stash pop. This will return those files to the working directory and allow you to work as before.

EDIT: A good link for learning all about the git stash command: Git Tools - Stashing and Cleaning