When I ran the reg cleaner in safe mode it told me all traces of avira were gone but when I restarted I saw there were 2 avira folders in the program data folder and some other files in another folder which I cant recall the name of .
How do you know that the Avira Registry Cleaner didn't get rid of everything, what was left?
That is not uncommon. After running the uninstall and the vendors cleaning tool, anything left over can be manually removed by right-clicking and choosing delete.
If that's the case how would I rectify it?
An 0x40000015 error can also be caused by a damaged/corrupted Windows system file.
In any case, that error is not specific to Avira....I know in the past that Malwarebytes had been reported to throw that error.
Sometimes you have to investigate and troubleshoot starting with the most simple....such as rebooting the computer after uninstall, running SFC, running anti-malware scans, performing a system restore, etc.