I had similar issues, i found that this was due to badly split Polys.

I actualy stage saved this tute and kept the Poly, Nurbs and SubDivs in seperate mb files. I have also found the Poly>Clean Up not to be so good and I normally just use it to highlight the issues, undo and try again.

My tip would be to go back to your Nurbs Model, covernt to poly and ensure that when your Combining that all your vertices match to the other your combining with. If not its time to plit out some polys.

I know the tute tells you to use Boolean>Intersection Operation, but this does make for quite an untidy join (imho). This does mean a lot of edge removals and vertices being joined, i prefer a Poly>Combine...

Here is my Finished one from the Tutorial: