The day after I'd read this story in PCPro about how the new version of Photoshop can remove unwanted items from photos (and watched the admittedly low resolution and grainy but nonetheless impressive Youtube video), I came across this post on OMG! Ubuntu which describes how a plug-in for the GIMP (written by somebody as a Phd project, it seems) can do the same.
[Update: the OMG! Ubuntu post seems to have gone. The Resynthesizer page is still up. Debian users can install the plug-in from the repository.]
After installing the plug-in, make a selection and go to Filters> Map> Resynthesize.
Simple as that.
Now you see it...
Now you don't...
UPDATE: Tutorial here.