Inclusion Criteria:

- Men or women, 18 years of age or older

- Non-small cell lung cancer (NSCLC) has been histologically or cytologically confirmed

- Has relapsed or refractory locally advanced (Stage IIIb) or metastatic (Stage IV)
NSCLC

- Failed one prior line of systemic antineoplastic therapy for Stage IIIb/IV NSCLC (one
additional prior line allowed if given as neoadjuvant, or adjuvant therapy to tumor
resection)

- Subject must have documented progressive disease (PD) since previous systemic
antineoplastic therapy

- Has measurable disease per Response Evaluation Criteria in Solid Tumors (RECIST)
criteria

- Has an ECOG performance status score of 0 or 1

- Has a life expectancy greater than 3 months

- Female subjects 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.

- Subjects (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.

- In countries where health authorities have approved the pharmacogenomic and protein
testing, subjects (or their legally acceptable representatives) must have signed an
informed consent for testing indicating that they agree to participate in the genetic
part and protein testing part of the study; participation in the genetic and protein
testing component is mandatory for testing, but optional for future research.

Exclusion Criteria:

- Has peripheral neuropathy of Grade 2 or greater intensity, as defined by the National
Cancer Institute (NCI) Common Terminology Criteria for Adverse Events (CTCAE Version
3.0)

- Previous treatment with VELCADE or Alimta

- Has received 2 or more prior lines of antineoplastic therapies for Stage IIIb/IV
NSCLC

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

- Has had significant weight loss (documented equal to or greater than 10% body weight
in the 6 weeks before randomization)

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

- Platelet count equal to or less than 100 × 10^9/L

- Hemoglobin equal to or less than 8.0 g/dL (80 g/L)

- Absolute neutrophil count (ANC) equal to or less than 1.5 × 10^9/L

- AST equal to or greater than 3 times the upper limit of the normal range (ULN)
or greater than 5 times the ULN for subjects with liver metastases

- ALT equal to or greater than 3 times ULN

- Calculated creatinine clearance equal to or greater than 45 mL/min

- Total bilirubin equal to or greater than 1.5 times ULN

- Myocardial infarction within 6 months before randomization or has New York Heart
Association (NYHA) 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 that have not been completely
resected or completely eliminated by radiation therapy and/or chemotherapy, or
clinical or radiographic evidence that they have recurred. Subjects with a history
of brain metastases are required to have had a brain computed tomography (CT) or
magnetic resonance imaging (MRI) scan conducted within 1 month of enrollment to
verify the continuing absence of brain metastases.

- Uncontrolled pleural effusion (defined as more than 2 pleuracentesis within 4 weeks
of the randomization)

- Active systemic infection requiring treatment

- Inability to interrupt aspirin or other nonsteroidal anti-inflammatory drugs (NSAIDs)
for a 5-day period (8-day period for long-acting agents, such as piroxicam)

- Unable or unwilling to take corticosteroids

- Other malignancy within the past 5 years. Exceptions for the following if treated and
not active:

- basal cell or nonmetastatic squamous cell carcinoma of the skin;

- cervical carcinoma in situ; or

- International Federation of Gynecology and Obstetrics (FIGO) Stage 1 carcinoma
of the cervix

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

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