This type if thing sometimes occurs because the objects that you're trying to combine are not closed, if you have originally made the shapes from NURBS and have converted them to poygons the ends will still be open (unless you've already dealt with that!!).
Try marquee selecting the verts where they converge at the top and bottom of your objects, chances are you will see that instead of just one vert you have as many as there are edges radiating from that point. All you have to do is merge them and you should be flying.
If you haven't already got your poly count up on your heads up display I would suggest you put it there (Display > Heads Up Display > Poly Count), it's a pretty important tool as it shows you what the model is made from and how many items you have selected.
Hope that helps,