Inclusion Criteria:

- Patients must be diagnosed with symptomatic multiple myeloma within the past 90 days
confirmed by the following:

- Bone marrow plasmacytosis with >= 10% plasma cells or sheets of plasma cells or
biopsy proven plasmacytoma which must be obtained within 4 weeks prior to
randomization

- Measurable levels of monoclonal protein (M protein): >= 1.0 g/dL on serum
protein electrophoresis or >= 200 mg of monoclonal light chain on a 24 hour
urine protein electrophoresis which must be obtained within 4 weeks prior to
randomization Please note that if both serum and urine m-components are present,
both must be followed in order to evaluate response

- Hemoglobin > 7 g/dL

- Platelet count > 75,000 cells/mm^3

- Absolute neutrophil count > 1000cells/mm^3

- Creatinine < 2.5 mg/dL and creatinine clearance (measured or calculated) >= 60 mL/min

- Bilirubin < 1.5 mg/dL

- SGPT (ALT) and SGOT (AST) =< 2.5 times the upper limit of normal

- No prior systemic therapy with the exception of bisphosphonates for multiple myeloma

- Prior glucocorticosteroid therapy for the treatment of multiple myeloma is not
permitted; prior systemic glucocorticosteroid use for the treatment of non-malignant
disorders is permitted; concurrent use after registration on the study should be
restricted to the equivalent of prednisone 10 mg per day; prior or concurrent topical
or localized glucocorticosteroid therapy to treat non-malignant comorbid disorders is
permitted

- Prior palliative and/or localized radiation therapy is permitted provided at least 4
weeks have passed from date of last radiation therapy to date of registration;
patients with prior solitary plasmacytoma treated with radiation therapy with
curative intent are eligible if the disease has now progressed to active multiple
myeloma meeting all the eligibility criteria for this protocol

- Patients must not have active, uncontrolled seizure disorder. Patients must have had
no seizures in the last 6 months

- Patients must not have uncontrolled intercurrent illness including uncontrolled
hypertension, symptomatic congestive heart failure, unstable angina, uncontrolled
cardiac arrhythmia, uncontrolled psychiatric illness or social situation that would
limit compliance with the study, or a prior history of Stevens Johnson Syndrome

- ECOG performance status 0, 1, or 2

- Patients with smoldering myeloma or monoclonal gammopathy of undetermined
significance are not eligible

- Patients must not have grade 2 or higher peripheral neuropathy due to other medical
conditions at the time of randomization

- Patients must not have active, uncontrolled infection

- Patients must not have a history of current or previous deep vein thrombosis or
pulmonary embolism regardless of whether or not the patient is receiving
anticoagulation therapy

- For patients registered prior to activation of Addendum # 6; patients must be
willing and able to take prophylaxis with either aspirin at 325 mg/day or
alternative prophylaxis with either low molecular weight heparin or Coumadin

- For patients registered after activation of Addendum # 6; patients entering the
expansion phase of the protocol, which tests anticoagulant prophylaxis, must be
able and willing to be randomized between aspirin at 325 mg/day and Coumadin

- Female patients MUST NOT be pregnant or breastfeeding; due to the potential
teratogenic properties of CC 5013, and the known teratogenicity associated with
thalidomide, the use of these drugs in this patient population is ABSOLUTELY
CONTRAINDICATED

- Females of childbearing potential (FCBP) must have a negative serum or urine
pregnancy test with a sensitivity of at least 25 mIU/mL within 10-14 days and again
within 24 hours prior to starting course 1 of lenalidomide; further, they must either
commit to continued abstinence from heterosexual intercourse or begin TWO acceptable
methods of birth control: one highly effective method (IUD, birth control pills,
tubal ligation or partner's vasectomy) and one additional effective method (condom,
diaphragm or cervical cap); FCBP must also agree to ongoing pregnancy testing; men
must agree to use a latex condom during sexual contact with a FCBP, even if they have
had a successful vasectomy starting 4 weeks prior to and while taking CC5013 or
thalidomide and for four weeks after discontinuing this therapy. A FCBP is a sexually
mature woman who: 1) has not undergone a hysterectomy or bilateral oophorectomy; or
2) has not been naturally postmenopausal for at least 24 consecutive months (i.e.,
has had menses at any time in the preceding 24 consecutive months); all patients must
be counseled by a trained counselor every 28 days about pregnancy precautions and
risks of fetal exposure

- Patients with a history of prior malignancy are eligible provided there is no active
malignancy and a low expectation of recurrence within 6 months