The only answer I've found about what to do in this situation is "sudo apt-get clean" - but it either didnt solve this issue at all, or solved it only partially (not completely!), and so I still was getting this issue even though I have removed this non-free package long time ago...
However, the following command has helped me to finally fix this problem:
sudo apt-get --purge remove <package_name>
For example:
sudo apt-get --purge remove libfaac0
(libfaac0 is the only non free package I have accidentally encountered during the recent days)
Hope that helps!