Primary Objectives:

1. To determine the maximum tolerated dose (MTD) of intravenous DTIC during the first 2 cycles (6 weeks) of treatment when administered in combination with a fixed dose of oral Lenalidomide in patients with metastatic malignant melanoma previously untreated with systemic chemotherapy.

Secondary Objectives:

1. To define the recommended Phase II doses of Lenalidomide and DTIC when administered as combination therapy.
2. To evaluate the safety and toxicity profile of combination Lenalidomide plus DTIC.
3. To evaluate the preliminary efficacy of combination Lenalidomide plus DTIC.

Lenalidomide is related to a drug called Thalidomide, which is not widely used because of certain side effects. Lenalidomide belongs to a family of drugs that work by acting on the body's immune system, so that it makes more "anti-inflammatory" cells. This type of cell is normally found in the body and is believed to help reduce the growth of cancer cells and slow down the production of new cancer cells.

DTIC is an anti-cancer drug. It is designed to cause cancer cell death by creating DNA breaks in the nucleus of the cells.

Before you can start treatment on this study, you will have what are called "screening tests". These tests will help the doctor decide if you are eligible to take part in the study. You will be asked questions about your medical history, and you will have a complete physical exam, which will included measurements of your temperature, pulse, blood pressure, respiratory (breathing) rate, weight and height. You will be asked about any surgeries you have had and any medications you are taking. Your ability to perform daily activities will be checked through simple physical tests (such as walking or squeezing a ball). You will also have blood drawn (about 1 tablespoon) for routine tests and tests to measure your thyroid hormones.

You will have an electrocardiogram (ECG - a test that measures the electrical activity of the heart). You will have a chest x-ray and CT scans of the chest, abdomen and pelvis (below the waist). You will be required to have a MRI or CT scan of the brain. If your doctor feels it is necessary, you may need CT scans of the head and neck or a bone scan. To perform the bone scan, a small dose of radioactive technetium is administered intravenously (IV--through a needle in your vein). The technetium will collect in the areas of bone involved with metastatic cancer to "light up" these areas on the bone scan. The results of these tests will show if you are eligible to participate in the study. Women who are able to have children must have a negative blood pregnancy test.

If you are still eligible to take part in the study, you will begin study treatment. You will take Lenalidomide by mouth every day for 2 weeks, followed by 1 week of "rest." This 21-day period is referred to as one "study cycle." You should only take Lenalidomide on an empty stomach. You should fast for 1 hour before and after taking Lenalidomide.

DTIC will be given by IV on Day 1 of every study cycle. Three dose levels of DTIC will be tested during this study. The first 3 participants will be given the first (lowest) dose level of DTIC. After the safety of this dose of DTIC is confirmed at the starting dose level, the next 3 to 6 participants will be given the second dose level of DTIC. After the safety of this new dose level is confirmed, the dose of DTIC will be increased to the third (highest) dose level tested in this study. When the highest DTIC dose is found that has the fewest side effects when given with Lenalidomide, 10 more patients will be treated at this best dose level. Patients on the lowest dose level will not have their doses changed once the highest well tolerated dose is found. Once a patient starts on a dose, it will not be increased.

You will receive treatment with Lenalidomide and DTIC on an outpatient basis at UT M.D. Anderson Cancer Center. At the start of each 21-day study cycle, you will come in to the clinic to receive a 14-day supply of Lenalidomide, and you will receive your dose of DTIC by IV. You will be provided with a study drug diary each time you are given your supply of Lenalidomide, to write down any side effects you experience.

During each study visit, you will have a physical exam (including measuring your weight), and your medical history will be recorded. Your doctor will ask you about any side effects you are experiencing. You should bring your study drug diary, any unused medication, and empty packages of medication to each study visit. Women who are able to have children will have a pregnancy test performed during the study visit at the beginning of each study cycle. You will have blood drawn (about 1 tablespoon) for routine tests. You will also repeat the performance status tests.

During your study visit at the beginning of Cycle 3 (about 6 weeks after starting treatment), you will be checked to see if the disease is responding to treatment. You will have a chest x-ray and CT scans of the chest, abdomen and pelvis. If your doctor feels it is necessary, you will also have an EKG for the heart and MRI of the brain. These tests may be done more often if your doctor feels it is necessary.

You will continue to receive treatment as long as the disease is shrinking or does not get worse, and the study doctor decides that it is safe to do so. You will be taken off study if the disease progresses or intolerable side effects occur.

If you are taken off study for any reason, you will be scheduled for a final study visit. You will have a physical exam and will be checked for side effects related to the study treatment. You will have a chest x-ray, CT scans, an ECG, and possibly an MRI as well.

You will have blood drawn (about 1 tablespoon) for routine tests. You will be asked about any new symptoms that you may have experienced after the treatment was stopped.

This is an investigational study. DTIC has been approved by the FDA for the treatment of metastatic melanoma. The FDA has authorized Lenalidomide for use in research only. Up to 28 participants will take part in this study. All will be enrolled at M. D. Anderson.

Inclusion Criteria:

• Patients must meet all of the following inclusion criteria to be eligible for enrollment into the study: Understand and voluntarily sign an informed consent document.
• Age >/= 18 years at the time of signing Informed Consent.
• Be able to adhere to the study visit schedule and other protocol requirements.
• Histological documentation of malignant melanoma with evidence of metastatic disease.
• For the 10 patients enrolled at the MTD, at least one measurable lesion must be present.
• ECOG performance status of 0,1,2.
• Laboratory tests within these ranges: a) Absolute neutrophil count >/= 1,500/microliter b) Platelet count >/= 100,000/microliter, c) Serum creatinine </= 1.5 mg/dL, d) Total bilirubin </= 1.5 mg/dL, e) AST (SGOT)/ALT (SGPT) </= 2 x upper limit of normal (ULN)
• Females of childbearing potential (FCBP)† must agree to use two reliable forms of contraception simultaneously or to practice complete abstinence from heterosexual intercourse during the following time periods related to this study. FCBP must have two negative pregnancy tests (sensitivity of at least 50 mIU/mL) prior to starting study drug. Male Subjects: Must agree to use a latex condom during sexual contact with females of childbearing potential while participating in the study and for at least 28 days following discontinuation from the study even if he has undergone a successful vasectomy.
• All acute toxic effects (excluding alopecia) of any prior therapy must have resolved to < or = to grade 1 (NCI CTCAE v3.0). (not listed in protocol synopsis)
• Patients must be able to take medications orally.

Exclusion Criteria:

• The presence of any of the following will exclude a patient from study enrollment: Pregnant or lactating females.
• Any serious medical condition, including psychiatric illnesses that will prevent the patient from signing the informed consent or place the patient at an unacceptable risk if he/she participates in the study.
• Prior treatment with systemic chemotherapy. Patients who have received prior immunotherapy, including thalidomide, or radiotherapy remain eligible. Lesions within a prior field of radiation may only be used as indicator lesions if there has been evidence of disease progression at that site.
• Prior history of malignancies (except for basal cell or squamous cell carcinoma of the skin or carcinoma in situ of the cervix or breast) unless the patient has been free of the disease for at least 3 years.
• Use of thalidomide or biologic response modifier therapy within 14 days of Day 1, Cycle 1.
• Prior >/= grade-2 allergic reaction to thalidomide.
• Prior desquamating rash while taking thalidomide.
• Any prior use of CC-5013.
• Concurrent use of any other anti-cancer agents.
• Radiation or surgical treatment of melanoma within 28 days of starting study treatment.
• Active infection.
• Central nervous system (CNS) metastases.
• Patients with >/= grade-2 neuropathy.
• Patients with known HIV positivity or AIDS-related illness.