Ok, you know where the bad stuff is in the registry; A new install, I wouldn't go that far just yet...
I would, export each registry key to a folder on my desktop, then I would consult with shane abdelete each key...
out deleting each key and restart the computer to see the results.
I would also verify each function of the links in the registry and also delete each file it points too
if you have or they point to other areas in your registry using this as an example but filled with code like {0000-0000-0000000-0000000} then go to that key and se where it points to and export it also and then delete it.
I can not see that video because I am here in china and youtube just isn't avaiable here. if you can capture some key screen elements and post them back here?
Also, it will be interesting to see the key strings, I think even shane will want to know what they are too..
their is another program on ubunta called rootkitty, have you heard of? try to download and run it using the method they suggests.. it seems viable option to finding any root kit problems... "I have never used it so I am afraid I can not comment except that in your case, I WOULD TRY IT!
A new install, I wouldn't go that far just yet...