Inclusion Criteria:

1. 18 yrs old or greater & have histologically or cytologically proven metastatic or
recurrent head & neck cancer & have failed at least 1 prior, but not more than 3
chemotherapeutic regimen. Patients who have recurred after previous surgery and/or
radiation may participate in this trial, & patients may have had prior neoadjuvant or
adjuvant therapy. No restriction is placed on the # of cycles (beyond 1) of prior
therapy, however, patients must not have received the combination of Gemcitabine &
Paclitaxel previously.

2. Patients with known brain metastases are eligible for this trial if disease has been
treated & the patient is clinically stable & documented by a stable or improved
pretreatment CT or MRI of the brain to evaluate CNS disease within 28 days prior to
registration.

3. Patients must have measurable OR non-measurable disease documented by CT, MRI, X-ray
or nuclear exam (FDG-PET). Measurable disease must be assessed within 28 days prior
to registration & non-measurable must be assessed within 42 days prior to
registration. Pleural effusions, ascites & lab parameters are not acceptable as only
evidence of disease.

4. Patients must have progressed after at least 1 prior chemotherapeutic regimen. Prior
biologic therapy or radiation is permitted; however, at least 2 wks must have elapsed
since completion of prior therapy & patients must have recovered from all associated
toxicities at time of registration.

5. At least 3 wks must have elapsed since surgery (thoracic or other major surgeries) &
patients must have recovered from all associated toxicities at time of registration.
Measurable or non-measurable disease must be present outside the area of surgical
resection.

6. Patients must have an ANC 1,500/µl & platelet count 100,000/µl obtained within 28
days prior to registration.

7. Patients must have adequate hepatic function documented by a serum bilirubin 1.5 x
institutional ULN & LFTs (SGOT or SGPT) 2.5 x the institutional ULN obtained within
28 days prior to registration.

8. All patients with pulmonary metastasis must have an FEV1 of > 1000 ml/min obtained
within 28 days prior to registration & must have PFTs with DLCO.

9. All patients must have a Zubrod Performance Status of 0,1 or 2.

10. Peripheral neuropathy, if present, must be Grade 1.

11. Patients must be informed of investigational nature of this study & must sign & give
written informed consent in accordance with institutional & federal guidelines.

Exclusion Criteria:

1. No other prior malignancy is allowed except for the following: adequately treated
basal cell or squamous cell skin cancer, in situ cervical cancer, adequately treated
Stage I or II cancer from which the patient is currently in complete remission or
other cancer from which the patient has been disease-free for 5 yrs.

2. Pregnant or nursing women may not participate in this trial because of the increased
risk of fetal harm including fetal death from the chemotherapeutic agents. Women/men
of reproductive potential may not participate unless they have agreed to use an
effective contraceptive method (hormonal or barrier method of birth control;
abstinence) prior to study entry & for 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.

3. Patients taking drugs that are strong inducers of the enzyme CYP3A4 including
anticonvulsants (i.e., phenytoin, phenobarbital, carbamazepine, or primidone) &
rifampin OR strong inhibitors of CYP3A4 (clarithromycin, itraconazole, and
ketoconazole) will be excluded from this study. Patients must be off these
medications for 2 wks in order to participate in this trial.