Oxaliplatin and Paclitaxel in Treating Patients With Locally Recurrent or Metastatic Cervical Cancer

Inclusion Criteria: * Patients must have histologically or cytologically confirmed squamous cell, adenosquamous cell or adenocarcinoma of the uterine cervix * Lesions must be metastatic to organs or lymph nodes outside the pelvis or must be locally recurrent in the pelvis after definitive therapy (surgery or radiation therapy) with at least 50% increase in size on sequential imaging studies * Patients must have measurable disease, defined as at least one lesion that can be accurately measured in at least one dimension (longest diameter to be recorded) as \>= 20 mm with conventional techniques or as \>= 10 mm with spiral CT scan * Patients may have received chemotherapy in conjunction with radiation therapy for primary, definitive therapy; patients may not have received treatment with cytotoxic agents for advanced or recurrent disease * Patients who have had chemotherapy, radiation therapy or surgery must allow four weeks for recovery of bone marrow or recovery from surgery/radiation * Life expectancy of greater than 2 months * ECOG performance status =\< 2 (Karnofsky \>= 60%) * Leukocytes \>= 3,000/uL * Absolute neutrophil count \>= 1,500/uL * Platelets \>= 100,000/uL * Total bilirubin within normal institutional limits * AST(SGOT)/ALT(SGPT) =\< 2.5 X institutional upper limit of normal * Creatinine within normal institutional limits * The effects of oxaliplatin on the developing human fetus at the recommended therapeutic dose are unknown; for this reason, women of child-bearing potential and men must agree to use adequate contraception (hormonal or barrier method of birth control; abstinence) prior to study entry and for the duration of study participation; should a woman become pregnant or suspect she is pregnant while participating in this study, she should inform her treating physician immediately * Ability to understand and the willingness to sign a written informed consent document Exclusion Criteria: * Patients who have had chemotherapy or radiotherapy within 4 weeks (6 weeks for nitrosoureas or mitomycin C) prior to entering the study or those who have not recovered from adverse events due to agents administered more than 4 weeks earlier * Patients may not be receiving any other investigational agents * Patients with known brain metastases should be excluded from this clinical trial because of their poor prognosis and because they often develop progressive neurologic dysfunction that would confound the evaluation of neurologic and other adverse events * History of allergic reactions attributed to compounds of similar chemical or biologic composition to oxaliplatin, cisplatin or carboplatin or paclitaxel or docetaxel * Uncontrolled intercurrent illness including, but not limited to, ongoing or active infection, symptomatic congestive heart failure, unstable angina pectoris, cardiac arrhythmia, or psychiatric illness/social situations that would limit compliance with study requirements * Pregnant women are excluded from this study because oxaliplatin is a platinating agent with the potential for teratogenic or abortifacient effects; because there is an unknown but potential risk for adverse events in nursing infants secondary to treatment of the mother with oxaliplatin and paclitaxel, breastfeeding should be discontinued if the mother is treated with oxaliplatin * Because patients with immune deficiency are at increased risk of lethal infections when treated with marrow-suppressive therapy, HIV-positive patients receiving combination anti-retroviral therapy are excluded from the study because of possible pharmacokinetic interactions with oxaliplatin or other agents administered during the study; appropriate studies will be undertaken in patients receiving combination anti-retroviral therapy when indicated