I know this post is abit old,, so you've probably found a solution.

I had this problem while doing the DRAGON TUTORIAL . The legs joined ok, but when it came to the wing it came up with the error you got. Suggesting that some edges were non-manifold. I spent hours selecting and moving vertices and edges to see what was going on. And in the end, for some reason I looked at the normals. Don't know why. But the normals on my seperate wing object were reversed (facing into the model) so I reversed the normals so they were facing out and then recombined the wing to the body, merged vertices. Then when I converted to Sub-D all was ok.

IN SHORT When you get errors to do with non-manifold geometry not converting, try looking at your face normals as well. The CLEANUP tool doesn't always work and doesn't offer anything to cleanup normals.

ABOUT BOOLEANS I don't know if what I did will work for you as you used a boolean, booleans are famous in all modelling programs for creating unexpected results.

HOW I DID IT When I joined my legs, to the body, the toes to the feet and the wing to the body I insert the object to be joined (wing) into the body slightly, then use SPLIT POLY on the body around the wing. Delete the faces not needed. Then combine, merge vertices and then convert.

It does show you both the boolean technique and the method I used above in the DRAGON TUTORIAL. But with any modelling it's a matter of personal preference.