Inclusion Criteria:

1. Patients must have a histologic or cytologic diagnosis of non-small cell lung cancer.
At the time of study entry, patients must have locally advanced (stage IIIb) or
metastatic (stage IV) disease.

2. Patients must have at least one site of either measurable or non-measurable disease.

3. Patients must not have received prior systemic chemotherapy for metastatic disease.
Prior adjuvant systemic chemotherapy is allowed. At least six (6) months must have
elapsed since any prior adjuvant systemic chemotherapy.

4. At least 6 weeks (42 days) since any prior immunotherapy, cytokine, biologic, vaccine
or other non chemotherapy anticancer systemic therapies, unless patients have
progressed during or after such therapy.

5. At least 4 weeks (28 days) since any prior radiotherapy to > 25% of the bone marrow.

6. Patients must have ECOG performance status of 0 - 2.

7. Patients must be at least 18 years of age.

8. Patients must have adequate hepatic and renal function.

9. Patients must have adequate bone marrow function.

10. Life expectancy of at least 3 months.

11. Patients must sign an informed consent form indicating that they are aware of the
investigational nature of this study and in keeping with the policies of their
institution.

Exclusion Criteria:

1. Patients who have received prior systemic chemotherapy in the adjuvant setting with a
treatment-free interval of less than six (6) months.

2. Patients who have a past or current history of neoplasms other than the entry
diagnosis, except for curatively treated non-melanoma skin cancer or carcinoma in
situ of the cervix and except for other cancers treated for cure and with a
disease-free survival greater than 5 years.

3. Patients with symptomatic brain metastasis(es).

4. Women who are pregnant or nursing and men or women who are not practicing an
acceptable method of birth control. Women may not breast-feed while on this study.

5. Patients with current active infections requiring anti-infectious treatment (e.g.,
antibiotics, antivirals, or antifungals).

6. Patients with current peripheral neuropathy of any etiology that is greater than
grade 1.

7. Patients with unstable or serious concurrent medical conditions.

8. Patients with a known hypersensitivity to Cremophor.

9. Patients with Gilbert's syndrome.

10. Patients must not have had major surgery within the past 14 days.

11. Patients must not receive any concurrent chemotherapy, radiotherapy, or immunotherapy
while on study.

12. No known HIV disease or infection.

13. Patients receiving ketoconazole, erythromycin, verapamil, diazepam, quinidine, or
diltiazem.