Inclusion Criteria:

- Documented diagnosis of 1 of the following:

- Myelodysplastic syndromes (MDS) lasting at least 3 months (MDS duration >= 3
months) according to World Health Organization (WHO) criteria or
non-proliferative chronic myelomonocytic leukemia (CMML) (white blood cells
[WBC] < 12,000/mcL)

- International prognostic scoring system (IPSS) category of low- or
intermediate-1-risk MDS as determined by cytogenetic analysis

- Cytogenetic analysis required if current bone marrow biopsy is a dry tap

- Patients with cytogenetic failure and < 10% marrow blasts are eligible

- Patients with cytogenetic failure must have prior cytogenetic results
(fluorescence in situ hybridization [FISH] is not a substitute) within 6
months after completion of the last type of MDS treatment (in this case,
growth factors are not considered a type of MDS treatment)

- Must have symptomatic anemia with hemoglobin < 9.5 g/dL =< 8 weeks prior to
randomization or with red blood cells (RBC) transfusion dependence (i.e., >= 2
units/month) confirmed for =< 8 weeks before randomization

- For patients without the deletion 5q 31.1, must have failed treatment with an
erythropoietic growth factor OR have a low probability of response to
rhu-erythropoietin, as defined by the following:

- Prior erythropoietin failure: requires ≥ 40,000 units epoetin alfa/week for 8
weeks or equivalent dose of darbepoetin alfa for 8 weeks and failed to achieve
transfusion independence (in transfusion-dependent patients) or failed to
achieve ≥ 2 g rise in hemoglobin sustained for ≥4 weeks (in
transfusion-independent patients)

- Low erythropoietin response profile: rhu-erythropoietin and epoetin alfa-naive
patients receiving ≥ 2 U pRBC/month for ≥ 8 weeks and serum erythropoietin ≥ 500
mU/mL in the 8 weeks prior to study randomization for a hemoglobin < 9.5 g/dL

- Patients must be off all non-transfusion therapy for MDS for 28 days prior to
initiation of study treatment, including all types of growth factors; patients may
receive hydrocortisone prophylactically to prevent transfusion reactions

- Patients must have a serum erythropoietin level documented before randomization and
=< 56 days before Day 1 of study treatment; NOTE: hemoglobin must be < 9.5 g/dL at
time that serum erythropoietin is drawn

- No documented iron deficiency

- Must have documented bone marrow iron stores (if marrow iron stain is not
available, transferrin saturation must be > 20% or serum ferritin > 100 ng/mL)

- Women must not pregnant or breastfeeding; females of childbearing potential 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 Cycle 1 of
lenalidomide; a female of childbearing potential(FCBP) is any woman, regardless of
sexual orientation or whether they have undergone tubal ligation, who meets the
following criteria: 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; FCBP must also
agree to ongoing pregnancy testing

- Effective contraception must be used by patients participating in lenalidomide
therapy, and all patients must agree to counseling by a trained counselor every 28
days about pregnancy precautions and risks of fetal exposure; females of childbearing
potential (FCBP) must either commit to continued abstinence from heterosexual
intercourse or begin TWO acceptable methods of birth control: one highly effective
method and one additional effective method AT THE SAME TIME, at least 28 days before
starting lenalidomide, during lenalidomide therapy, during dose interruptions, and
for at least 28 days following childbearing potential should be referred to a
qualified provider of contraceptive methods, if needed; males receiving lenalidomide
must agree to use a latex condom during any sexual contact with females of
childbearing potential even if they have undergone a successful vasectomy

- Patients must not have prior therapy with lenalidomide

- Patients must not have a diagnosis of uncontrolled seizures or uncontrolled
hypertension

- Patients must not have proliferative (WBC >= 12,000/mcL) chronic myelomonocytic
leukemia (CMML); WBC must be < 12,000/mcL

- Patients must not have MDS secondary to treatment with radiotherapy, chemotherapy,
and/or immunotherapy for malignant or autoimmune diseases

- Platelet count >= 50,000/mcL (without platelet transfusion)

- Absolute neutrophil count (ANC) >= 500 cells/mcL (must be >= 500/mcL without myeloid
growth factor support)

- Serum creatinine =< 1.5 times upper limit of normal (ULN)

- Serum glutamic oxaloacetic transaminase (SGOT)/aspartate aminotransferase (AST) or
serum glutamic pyruvate transaminase (SGPT)/alanine aminotransferase (ALT) =< 2.0 x
ULN

- Serum total bilirubin < 3.0 mg/dL

- Prior thalidomide allowed, however, patients must not have prior >= grade-3 allergic
reactions to thalidomide

- Patients must not have prior history of desquamating rash from thalidomide at time of
study entry

- Patients must not have clinically significant anemia resulting from iron, B12 or
folate deficiencies, autoimmune or hereditary hemolysis, or gastrointestinal bleeding

- Patients must not have used cytotoxic chemotherapeutic agents or experimental agents
(agents that are not commercially available) for the treatment of MDS within 8 weeks
of randomization

- Patients must not have prior history of malignancy other than MDS (except basal cell
or squamous skin cell carcinoma or carcinoma in situ of the cervix or breast) unless
the subject has been confirmed free of disease for >= 3 years

- Patients must not have any serious medical condition or any other unstable medical
co-morbidity, or psychiatric illness that will prevent the subject from signing the
informed consent form or will place the subject at unacceptable risk if he/she
participates in the study

- Patients must not have a history of thrombo-embolic events within 3 years prior to
study randomization

- Patients must not have known human immunodeficiency virus (HIV)-1 seropositivity
because HIV can be an alternate cause of anemia

- Patients must not have a known allergic reaction to epoetin alfa (Procrit) or human
serum albumin

- Patients must have completed 16 weeks of monotherapy with lenalidomide

- Patients must show failure to achieve MER (major erythroid response) or have achieved
MER but relapsed on Arm A

- Patients must not have a limiting unresolved grade 3 or greater toxicity from
lenalidomide monotherapy or drug intolerance preventing continuation of lenalidomide
treatment