Inclusion Criteria:

- Patients must have histologically or cytologically proven selected stage IIIB (T4
lesion due to malignant pleural effusion) or stage IV, advanced non-small cell lung
cancer or recurrent disease after previous surgery and/or radiation

- Patients with known brain metastases are not eligible for this clinical trial because
of their poor prognosis and because they often develop progressive neurologic
dysfunction that would confound the evaluation of neurologic and other adverse
events; all patients must have a pretreatment CT or MRI scan of the brain to evaluate
for CNS disease within 28 days prior to registration

- Patients must have measurable OR non-measurable disease documented by CT, MRI, or
x-ray; measurable disease must be assessed within 28 days prior to registration and
non-measurable disease must be assessed within 42 days prior to registration; pleural
effusions, ascites and laboratory parameters are not acceptable as the only evidence
of disease

- Patients must not have received any prior systemic chemotherapy or biological agent
for non-small cell lung cancer; prior radiation is permitted; however, two weeks must
have elapsed since the completion of prior radiation therapy and patients must have
recovered from all associated toxicities at the time of registration; measurable or
non-measurable disease must be outside the previous radiation field or a new lesion
inside the port must be present

- At least two weeks must have elapsed since surgery (thoracic or other major
surgeries) and patients must have recovered from all associated toxicities at the
time of registration

- Serum creatinine =< the institutional upper limit of normal OR a creatinine clearance
>= 60 cc/min; these tests must have been performed within 28 days prior to
registration

- ANC >= 1500/ul obtained within 14 days prior to registration

- Platelet count >= 100,000/ul obtained within 14 days prior to registration

- Serum bilirubin =< institutional upper limit of normal obtained within 28 days prior
to registration

- SGOT or SGPT =< 2.5 x the institutional upper limit of normal obtained within 28 days
prior to registration

- All patients must have a Zubrod performance status of 0-1

- Peripheral neuropathy, if present, must be =< grade 1 (NCI Common Terminology
Criteria for Adverse Events version 3.0)

- Correlative science studies: Institutions must have IRB approval of S9925 (the Lung
Cancer Specimen Repository); patients must be offered participation in S9925; with
the patient's consent, tumor tissue, blood and plasma will be submitted for testing
via S9925; patients must be registered separately to S9925 in order for institutions
to receive credit for specimen submissions

- Patients known to be HIV positive and receiving anti-retroviral therapy (HAART) are
not eligible for this study because of possible pharmacokinetic interactions

- Patients must not be planning to receive any other concomitant anticancer treatment
including chemotherapy, radiation therapy, biologic agents or any other
investigational drugs

- Patients should not have known hypersensitivity to boron, mannitol, or PS-341; if day
28 or 42 falls on a weekend or holiday, the limit may be extended to the next working
day; in calculating days of tests and measurements, the day a test or measurement is
done is considered day 0; therefore, if a test is done on a Monday, the Monday four
weeks later would be considered day 28; this allows for efficient patient scheduling
without exceeding the guidelines

- 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 years

- 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

- Patients must be informed of the investigational nature of this study and must sign
and give written informed consent in accordance with institutional and federal
guidelines

- At the time of patient registration, the treating institution's name and ID number
must be provided to the Data Operations Center in Seattle in order to ensure that the
current (within 365 days) date of institutional review board approval for this study
has been entered into the data base