Union fails on two closed, intersecting polysurfaces in the attached, using
Version 5 (5.1.30129.1756, 1/29/2013)
This kind of thing will classically give you problems, anytime you have a curved surface that attempts to match to a flat surface in a near-tangent condition is likely to fail. To see why it does, run Intersect between the two objects. There are intersections all over the place - Rhino can't figure out a clean cutting line because the surfaces overlap - but they're not really co-planar.
The way to approach this is the good old manual method -
1) First use Cap to close the (open) left hand object (viewed from the top)
2) DupEdge one of the borders of the right hand object. With the resulting curve, in Top view, use Trim to cut away the unwanted part of the left hand object. You can then delete the curve.
3) ExtractSrf the side surface of the right hand object - the part that is touching the left.
4) Use Split to split the extracted surface with the left hand object. Delete the center (inside) part of the surface resulting from the split.
5) Select all the parts and run Join. It should (in this case) join up into a closed polysurface.
If if does not close, you can go looking for naked edges. Naked edges will indicate where things don't meet within tolerance. You may need to adjust your design so that they do.
'Sorry about the open left-hand object. In order to simplify the example, I trimmed off most of the left-hand solid, but neglected to recap it. I'll try your remaining suggestions on the full model.
Okay, that worked with no naked edges. Thanks!