How are you saving down?
Some people prefer to explode everything, then export directly to 2004 or 2000. I have had mixed results with that method. I've had C3D take forever on a drawing when I try to explode everything, but it will Export just fine. Other times, the Explode method seems to work fine, and is not as annoying as a two-phase export. Like many things in C3D, it can end up being trial and error until something works.
Also, if you have background masks, you may want to make sure you have a white background (for most people, this means switch to paperspace) before doing the export. Background masks in C3D are implemented with HATCH objects, and they take on the current background color when you export. So if you export while the background is white, they turn into solid white hatches, and everything still prints for the recipient. If you export from modelspace (with the typical black background), the background masks will turn into black hatches, and print as giant black blobs for your recipient.
Exporting data from C3D can be an unfortunately-troublesome experience...