The Shapeways servers are usually able to handle so-called 'multiple shell' objects and intersecting or overlapping objects. If your object is not accepted, you can try to manually 'fuse' the parts together using Boolean operations.
Once you've got all your meshes manifold, make sure that every mesh is its own object. You can't do boolean operations between meshes within one object. You can split part of a mesh into its own object by selecting all the vertices in the mesh and hitting the P key. Selecting a single vertex and then holding down ctrl-+ will select all attached vertices. To separate each mesh in the current object at once, press P and select 'All Loose Parts'.
Once you have all meshes in their own objects and manifold, save and create a copy of the blender file for making the printable version. I also set Blender to keep the past 10 saved versions because I'm paranoid - I like being able to go back and retrieve older versions of the meshes if I screw up beyond the undo threshold.
Open the copy of the file, and select each object, one at a time. In object mode, apply all modifiers, then switch to Edit mode, hit A once or twice to select all vertices, then press ctrl-T to triangulate all faces. I don't know why, but Blender does a much better job with Boolean operations if the meshes are triangulated.
Back in object-mode, select any two overlapping meshes, press w and select "Union", which will combine them into a single mesh (it doesn't delete the originals, though). This process could take a while. Once it's all done, select the two original objects that were combined, and either move them to another layer, or delete them to get them out of the way (I delete them, but that's why I keep the last ten saved copies). Select the new combined object, switch to edit mode, select none (A key once or twice), then select non-manifold (ctrl-alt-shift-M). Resolve all non-manifold, many of them will be easy to fix, and often a union will result in a manifold mesh, but not always, so always, always check - if you move on and try to do another union with a mesh that is non-manifold, you will have problems. Check for manifold EVERY TIME. After that, select-all and triangulate so your combined mesh is both manifold and fully triangulated so it's ready for the next union, if necessary.
If you have two meshes that have a widely disparate density of vertices, like an organic mesh being unioned with an eight-vertex cube, subdivide the one with the lower density and then triangulate. For some reason, Blender does not like doing these types of unions - it will chug away for hours and hours and probably never finish.
Save every time you perform a union then resolve the non-manifolds.