Inclusion Criteria:

1. Histologic Documentation: Histologic or cytologic diagnosis of distant metastatic
melanoma and clinical evidence of brain metastasis.

2. Pts must have brain lesions of =/> 1.0cm longest dimension by magnetic resonance
(MRI) or spiral computed tomography (CT), if MRI not feasible or > 0.5cm by MRI with
3D images. Patients with/without extracranial disease are eligible. Measurable
extracranial disease is not required. Lesions that are considered non-measurable
include: <1.0 cm by MRI or Spiral CT, Bone lesions, Leptomeningeal disease, Ascites,
Pleural/pericardial effusion, Lymphangitis cutis/pulmonis, Abdominal masses that are
not confirmed and followed by imaging techniques, Cystic lesions, lesions that are in
a previously irradiated area, unless new growth can be documented.

3. Age >/= 18 years of age.

4. Eastern Cooperative Oncology Group (ECOG) Performance Status: 0 or 1

5. No more than 1 prior chemotherapy regimen and no prior chemotherapy for brain
metastases. No prior treatment with continuous daily dose of temozolomide; prior
immunotherapy and surgical resection are permitted. Patients with prior history of
whole brain radiotherapy (WBRT) and stereotactic radiosurgery (SRS) are permitted
providing that there is measurable lesion with documented growth post radiation or
new disease.

6. (#5 continued) Progression of lesions treated with WBRT must be shown by 2 post
treatment brain imaging at least 3 weeks apart. Progression of disease is also
considered when the patient had increase of lesions as per MRI of brain obtained 4
weeks or more after WBRT completed when compared to baseline MRI obtained less than 1
week prior to start of radiation. Lesions treated with SRS must have responded and
then progressed.

7. The following time periods must have elapsed since prior therapy: 3 weeks since
surgical resection or stereotactic radiosurgery; 4weeks since prior whole brain
radiation therapy; 6 weeks since prior nitrosureas or mitomycin C. Biologic agents
used as adjuvants and vaccines or cellular therapies will not require 4-week wash out
period if the patient meets all eligibility criteria.

8. No frequent vomiting and/or medical condition that could interfere with oral
medication intake (e.g., partial bowel obstruction).

9. No other concurrent chemotherapy/immunotherapy/radiotherapy.

10. No history of active angina or myocardial infarction within 6 months. No history of
significant ventricular arrythmia or uncontrolled arrythmia or bradycardia. The study
participants must have resting heart rate of 48 or greater (.e.i - to receive
Thalidomide).

11. No prior history of deep vein thrombosis (DVT) or pulmonary embolism (PE).

12. No known HIV disease. Patients with a history of intravenous drug abuse or any other
behavior associated with an increased risk of HIV infection should be tested for
exposure to the HIV virus. Because peripheral neuropathies are a common toxicity of
antiviral therapy and of viral infection in HIV patients, as well as a common
significant toxicity with thalidomide, patients who test positive or who are known to
be infected are not eligible. An HIV test is not required for entry on this protocol,
but is required if the patient is perceived to be at risk.

13. No pre-existing neuropathy that is >/= grade 2, including uncontrolled seizures.

14. No expected need for radiotherapy to brain or any extracranial metastatic site during
the period of participation in the study.

15. Patients may not be taking Coumadin, warfarin or heparin products or their
derivatives.

16. Patients who require anti-platelet therapy such as daily aspirin, Plavix or ibuprofen
are not eligible to participate.

17. Patients requiring the use of bisphosphonates (e.g., zolendronic acid) are not
eligible to participate. Patients who receive thalidomide in combination with
zolendronic acid are potentially at increased risk of renal dysfunction.

18. Required Initial Laboratory Data: Granulocytes >/= 1,500/ml; Platelet count >/=
100,000/ul; Creatinine normal; Alkaline phosphatase Serum beta-HCG Negative (in female patients unless S/P hysterectomy or menopausal or
no menses for 24 months). Assay must have a sensitivity of at least 50 mIU/ml. Serum
anticonvulsant levels (for patients on a measurable anticonvulsant) must be within
therapeutic range. Electrocardiography (EKG) must be without acute abnormalities or
uncontrolled arrhythmia.

19. Pregnant and nursing women are not eligible for treatment on this protocol. Women of
childbearing potential must agree to abstain from all intercourse or use two methods
of birth control for 28 days prior to treatment and while under treatment with
thalidomide and for 4 weeks after completing therapy. One of the methods of birth
control must be highly active (IUD, hormonal, tubal ligation or partner's vasectomy)
and used concomitantly with one additional method(e.g., latex condom, diaphragm or
cervical cap. Please see also eligibility criteria 19 and 20.

20. In addition, women of childbearing potential must have morning urine b-HCG performed
within 1 week prior to registration and within 24 hours before beginning study
treatment. All the precautions for childbearing potential women are required even in
patients with infertility unless due to hysterectomy or the patient has been post
menopausal (has had no menses for at least 24 consecutive months). Men must agree to
abstain from unprotected sexual intercourse. Male patients should request that female
partners use a second method of birth control in addition to the male barrier method
(condoms).

21. All patients (men and women) must agree to use medically approved contraceptive
measures simultaneously prior to starting thalidomide therapy, all during drug
therapy, and for at least 1 month after therapy has stopped. Women of childbearing
potential should start using medically approved contraceptive measures 4 weeks prior
to starting thalidomide therapy.

22. Patients must give written consent.

23. Patients must be willing and able to comply with the FDA-mandated S.T.E.P.S version 3
program.

Exclusion Criteria:

1. Presence of any ongoing toxic effect from prior treatment.

2. Serious infection requiring intravenous antibiotics, or nonmalignant medical
illnesses that are uncontrolled or whose control may be jeopardized by the
complications of this therapy.

3. Concurrent active malignancy other than non-melanoma skin cancers or
carcinoma-in-situ of the cervix. Patients with previous malignancies, but which have
not required anti-tumor treatment within the preceding 24 months will be allowed to
enter the trial. Patients with a history of a T1a or b prostate cancer (detected
incidentally at Transurethral resection of the prostate (TURP) and comprising less
than 5% of resected tissue) may participate if the Prostate-specific antigen (PSA)
remained within normal limits since TURP.

4. Any other medical condition or reason that, in the principal investigator's opinion,
makes the patient unsuitable to participate in a clinical trial including but not
limited to active bleeding, prior surgical procedures affecting absorption or
gastrointestinal tract disease resulting in inability to take oral medication.

5. Pregnant and lactating women.