Inclusion Criteria:

- Histologically confirmed non-small cell lung cancer (NSCLC)(squamous cell,
adenocarcinoma, large cell, or bronchoalveolar carcinoma)

- Stage IIIB NSCLC with pleural effusion, Stage IV NSCLC, or recurrent disease
following surgery with or without radiation therapy

- Available paraffin-embedded tissue to measure the expression levels of βIII tubulin

- Disease measurable by Response Evaluation Criteria in Solid Tumors, with at least 1
target lesion situated outside any previous radiotherapy field

- Karnofsky performance status of 70-100

- Life expectancy of at least 3 months

- Men and women, ages 18 years and older

Exclusion Criteria:

- Uncontrolled brain metastases

- Peripheral neuropathy greater than Grade 1

- Fewer than 4 weeks from prior radiation therapy or locoregional surgeries to
randomization date (less than 1 week from focal/palliative radiotherapy or minor
surgery)

- Any concurrent malignancy other than nonmelanoma skin cancer or carcinoma in situ of
the cervix

- Known HIV-positive status

- Absolute neutrophil count lower than 1500 cells mm^3

- Total bilirubin level higher than upper limit of normal (ULN) as defined by the
institution (with the exception of elevation due to Gilbert's syndrome)

- Aspartate transaminase or alanine transaminase level higher than 2.5*ULN

- Serum creatine level of 1.5 mg/dL or higher

- Renal function with a creatinine clearance of less than 50 mL/min (as calculated with
the Cockcroft and Gault equation)

- Any prior antineoplastic systemic regimens.