Comment 11 for bug 1040380

The update wouldn't apply for me, either with apt-get upgrade or apt-get --reinstall, because it tries to configure update-notifier-common (and fails) before updating it.

But manually editing /usr/lib/update-notifier/package-data-downloader to replace lines like "if para.has_key('should-download'):" with "if 'should-download' in para:", as Julian said above, allowed the update to apply. (I didn't want to try removing it because apt-get was going to remove other packages.)