I don't have any free applications to reccomend, but DeskArtes 3Data Expert and Magics 13 have come a long way in making these sort of errors easier to spot and rectify. Though there aren't any that will automatically fix it.
Z-Corp's ZEdit would also be able to do it (it contain tons of code from the DeskArtes program).
If the Tutorial wasn't able to help, upload an STL of your model or PM it to me and I will take a look. There are so many different situations that can cause a non-manifold issue so I can understand your frustration.