Inclusion Criteria:

- Men or women, 18 years of age or older.

- NSCLC histologically or cytologically confirmed.

- Locally advanced (Stage IIIB) or metastatic (Stage IV) NSCLC.

- No prior systemic anti-neoplastic therapy for Stage IIIB/IV NSCLC (one prior line is
allowed if given as adjuvant or neo-adjuvant therapy).

- Measurable disease per RECIST criteria.

- ECOG performance status score of 0 - 1.

- Life expectancy greater than 3 months.

- Female patients must be postmenopausal (for at least 6 months), surgically sterile,
abstinent, or, if sexually active, be practicing an effective method of birth control
(e.g., prescription oral contraceptives, contraceptive injections, intrauterine
device, double-barrier method, contraceptive patch, male partner sterilization)
before entry and throughout the study; and have a negative serum or urine β-human
chorionic gonadotropin (hCG) pregnancy test at screening.

- Patients (or their legally acceptable representatives) must have signed an informed
consent document indicating that they understand the purpose of and procedures
required for the study and are willing to and able to comply with the protocol
requirements and participate in the study before any study-related procedure not part
of normal medical care is conducted.

- Patients (or their legally acceptable representatives) must have signed an informed
consent for testing indicating, that they agree to participate in the correlative
marker part of the study.

Exclusion Criteria:

- Peripheral neuropathy of Grade 2 or greater intensity, as defined by the NCI Common
Terminology Criteria for Adverse Events (CTCAE Version 3.0).

- Previous treatment with VELCADE.

- Prior systemic anti-neoplastic therapies for Stage IIIB/IV NSCLC except if as
neoadjuvant therapy for Stage IIIB.

- Any prior systemic anti-neoplastic therapy for NSCLC (i.e., prior chemotherapy,
radiation therapy, prior monoclonal antibodies or any investigational drug or any
major surgery) within 4 weeks before enrollment.

- Significant weight loss (documented < 10% body weight in the 6 weeks before
enrollment).

- Inadequate organ function at the screening visit as defined by the following
laboratory values:

- Platelet count ≤ 100 x 109/L

- Hemoglobin ≤ 8.0 g/dL (80 g/L)

- Absolute neutrophil count (ANC) ≤ 1.5 x 109/L

- AST ≥ 3 times the upper limit of the normal range (upper normal limit) or > 5
times the upper normal limit for subjects with liver metastases

- ALT ≥ 3 times ULN or > 5 times the upper normal limit for subjects with liver
metastases (Calculated creatinine clearance ≥ 45 mL/min, Total bilirubin ≥ 1.5
times Upper normal limit)

- Myocardial infarction within 6 months before randomization or has New York Heart
Association Class III or IV heart failure, uncontrolled angina, severe uncontrolled
arrhythmias, or electrocardiographic evidence of acute ischemia or active conduction
system abnormalities.

- Central nervous system metastasis or brain metastases unless patients have been
subjected to local radiation therapy and are clinically stable. Brain computed
tomography or magnetic resonance imaging is required in symptomatic patients to rule
out brain metastases but is not required in asymptomatic patients.

- Serious medical condition (such as severe hepatic impairment, pericardial disease,
acute diffuse infiltrative pulmonary disease, systemic infections etc) or psychiatric
illness likely to interfere with participation in this study

- Other malignancy within the past 5 years. Exceptions for the following if treated and
not active: basal cell or non-metastatic squamous cell carcinoma of the skin,
cervical carcinoma in situ or International Federation of Gynecology and Obstetrics
Stage 1 carcinoma of the cervix.

- History of allergic reaction attributable to compounds containing boron or mannitol.

- Pregnant or breast-feeding.

- Currently enrolled in another clinical research study or has received an
investigational agent for any reason within 4 weeks before randomization.