Sometimes upstream packages contain files of which the license (e.g. Artistic) or form (e.g. source-less binary) does not comply with the Free System Distribution Guidelines. This can't be fixed with a patch because the source would still contain the offending files. The solution is to modify the upstream tarball (a.k.a. the pristine source) and repackage it.
Before you start, make sure you have set up your environment.
First download the source package.
apt-get source --download-only my-program
Extract only the upstream source and make the necessary changes.
tar -xf my-program_1.0.orig.tar.gz rm my-program-1.0/path/to/bad/file
Wrap it back up, but with a name that makes it clear that this source is no longer pristine.
tar -czf my-program_1.0+fsdg.orig.tar.gz my-program-1.0/
Now add the packaging information to the source and update the changelog with the version and the reason for your change.
cd my-program-1.0 tar -xf ../my-program_1.0-1.debian.tar.gz dch -i
So the changelog entry should look like this:
my-package (1.0+fsdg-1gnewsense1) parkes; urgency=low * Remove non-free foobar implementation. (Closes: #123456) -- Joe Black <email@example.com> Sat, 26 Jan 2013 15:27:52 +0100
Note that we don't have an unstable suite and use the name of the target suite instead. The version string should be identical to the last Debian version except for the +fsdg and gnewsense1 parts.
The rest of the workflow is the same as patching a normal package from updating the control file onwards. You may have to edit some of debian/patches if the package doesn't build.