I've had similar issues in the past. I don't know of any sure fire way to help. Does the part check OK before you export?
You might try exporting as Parasolid first, reimporting and exporting as STEP. Or it might work to export your STEP file as Parasolid, reimport, and then export as STEP again. As a last desperate attempt, you might try IGES out and back in before exporting as STEP, or even IGES out and back, Parasolid out and back before exporting.