Inclusion Criteria:

- Histologic or cytologic diagnosis of squamous cell head and neck cancer

- Recurrent disease (locally advanced or metastatic)that is not amenable to local
therapy, (i) with at least 6 months since completion of systemic therapy
(chemotherapy or biological anticancer therapy), and (ii) with no more than 1
prior multimodal therapy (such as concurrent chemoradiation with or without
sequential chemotherapy) for locally advanced HNC tumor, and (iii) with no prior
systemic therapy (chemotherapy or biological anticancer therapy) for metastatic
disease; OR

- Newly diagnosed distant metastatic disease (Stage IVc)

- Prior therapies:

- Radiation therapy must be completed at least 4 weeks before study enrollment.
For palliative therapy, prior radiation therapy allowed <25% of the bone marrow
and prior radiation to the whole pelvis is not allowed. Patients must have
recovered from the acute toxic effects of the treatment prior to study
enrollment.

- Surgery (excluding prior diagnostic biopsy) must be completed at least 4 weeks
before study enrollment. Patients must have fully recovered from any acute
effects of surgery prior to study enrollment.

- An estimated life expectancy of at least 12 weeks.

- Eastern Cooperative Oncology Group (ECOG) performance status 0 or 1.

- Biological tissue available for biomarker analysis on tumor tissue.

- Disease status must be measurable as defined by RECIST. The index lesion must not be
in a prior irradiated area. Positron emission tomography (PET) scans and ultrasounds
may not be used for lesion measurements.

- Patient compliance and geographic proximity that allow for adequate follow-up.

- Adequate organ function as defined by the following:

- Bone marrow reserve: absolute neutrophil (segmented and bands) count (ANC)
greater than or equal to 1.5 × 109/L, platelets greater than or equal to 100 ×
109/L, and hemoglobin greater than or equal to 9 g/dL.

- Hepatic: bilirubin less than or equal to 1.5 × the upper limit of normal (ULN);
alkaline phosphatase (ALP), aspartate aminotransferase (AST), and alanine
aminotransferase (ALT) less than or equal to 3.0 × ULN (ALP, AST, and ALT less
than or equal to 5.0 × ULN is acceptable if the liver has tumor involvement).

- Renal: calculated creatinine clearance (CrCl) greater than or equal to 60
mL/min.

- For women: Must be surgically sterile, postmenopausal, or compliant with a medically
approved contraceptive regimen during and for 6 months after the treatment period;
must have a negative serum or urine pregnancy test within 7 days before study
enrollment, and must not be breast-feeding. For men: Must be surgically sterile or
compliant with a contraceptive regimen during and for 6 months after the treatment
period.

Exclusion Criteria:

- Have received treatment within the last 30 days with a drug that has not received
regulatory approval for any indication at the time of study entry.

- Are receiving concurrent chronic systemic immune therapy, or chemotherapy for a
disease other than cancer.

- Concurrent administration of any other antitumor therapy.

- Known prior allergic/hypersensitivity reaction to any of the components of the study
treatment.

- Serious concomitant systemic disorder (for example, active infection) or psychiatric
disorder that, in the opinion of the investigator, would compromise the patient's
ability to complete the study.

- Have serious cardiac disease, such as symptomatic angina, unstable angina, or the
history of myocardial infarction in the previous 12 months.

- Second primary malignancy that is clinically detectable at the time of consideration
for study enrollment.

- Have had another primary malignancy other than HNC, unless that prior malignancy was
treated at least 2 years previously with no evidence of recurrence. Exception:
Patients with a history of in situ carcinoma of the cervix, nonmelanoma skin cancer,
or low-grade (Gleason score less than or equal to 6) localized prostate cancer will
be eligible even if diagnosed and treated less than 2 years previously.

- Nasopharyngeal, paranasal sinus, lip, or salivary gland cancer.

- Presence of clinically significant (by physical exam) third-space fluid collections;
for example, ascites or pleural effusions that cannot be controlled by drainage or
other procedures prior to study entry.

- Have peripheral neuropathy of Common Terminology Criteria for Adverse Events (CTCAE)
Grade 1 or higher.

- Have central nervous system (CNS) metastases (unless the patient has completed
successful local therapy for CNS metastases and has been off corticosteroids for at
least 4 weeks before starting study therapy). Brain imaging is required in
symptomatic patients to rule out brain metastases, but is not required in
asymptomatic patients.

- Inability to interrupt aspirin or other nonsteroidal anti-inflammatory agents, other
than an aspirin dose less than or equal to 1.3 grams per day, for a 5-day period
(8-day period for long-acting agents, such as piroxicam).

- Unable or unwilling to take folic acid, vitamin B12, or prophylactic corticosteroids.

- Recent (within 30 days before enrollment) or concurrent yellow fever vaccination.