Comment 19 for bug 1570141

$ sudo chown -R _apt:root /var/lib/update-notifier/package-data-downloads/partial/
(note the addition of the -R flag)

in the top line should address the need to remove all files from partial (and maybe even the FAILED files), as _apt should have access to remove or overwrite those files.

I'm not sure why you would have to reinstall update-notifier-common more than once though, assuming all rights are appropriately in place. Maybe your internet connection timed out or checksums didn't match properly in the downloaded packages? Glad you got it working though.