Inclusion Criteria:

- Histologically or cytologically confirmed non-small cell lung cancer

- Mixed tumors allowed unless small cell elements are present

- Stage IIIB or IV or recurrent disease

- At least 1 measurable lesion ≥ 20 mm by conventional techniques OR ≥ 10 mm by spiral
CT scan

- No known brain metastases

- Performance status - ECOG 0-1

- More than 3 months

- Absolute neutrophil count ≥ 1,500/mm^3

- Platelet count ≥ 100,000/mm^3

- Bilirubin ≤ 2 mg/dL

- AST and ALT ≤ 2.5 times upper limit of normal (ULN) (5 times ULN if liver
involvement present)

- Creatinine ≤ 2 mg/dL

- Creatinine clearance ≥ 60 mL/min

- No symptomatic congestive heart failure

- No unstable angina pectoris

- No cardiac arrhythmia

- Not pregnant or nursing

- Negative pregnancy test

- Fertile patients must use effective contraception

- No peripheral neuropathy > grade 1

- No other concurrent uncontrolled illness

- No ongoing or active infection

- No psychiatric illness or social situation that would preclude study participation

- No more than 1 prior chemotherapy regimen

- Two prior chemotherapy regimens allowed provided 1 of the 2 regimens was
gefitinib monotherapy as second-line therapy

- At least 4 weeks since prior chemotherapy (6 weeks for carmustine, mitomycin, or
nitrosoureas) and recovered

- At least 4 weeks since prior radiotherapy (except localized radiotherapy for symptom
relief) and recovered

- Prior bortezomib allowed provided patient achieved at least a partial response (of at
least 6 months duration), received no other therapy since the last dose of
bortezomib, and has no residual toxicity greater than grade 1

- No other concurrent investigational or commercial agents or therapies for malignancy