Does it happens on files from the same type, mainly, video or sound files?
When you uninstalled Norton, did you make sure it uninstalled the Norton Unerase (or whatever it is called). Norton has this improved recycle bin that is not always gets uninstalled when you uninstall the rest of the Norton products.
