I figured out an annoying fix after trying to wipe davl, data, etc., to no avail...
I have to download and install Root Explorer (which thankfully didn't give me the error message), then I had to delete individual program folders that persisted even after a full wipe of the devise. I deleted these files from the /Data/Data folder which contains hundreds of these folders.
Does anyone have a better way to permanently delete these files rather than going in an removing them one at a time?
I've had this problem both on Stock Rooted NC5 and on Galaxy Note fre3 Hybrid De[Odex] v2.14 -BeastMode Kernel