Aldesleukin With or Without Vaccine Therapy in Treating Patients With Stage IV Melanoma

Inclusion Criteria: * Stage IV melanoma. * Prior systemic chemotherapy, immunotherapy, or biological therapy is allowed if at least 4 weeks since last treatment. Patient must recover from the acute toxic effects of the treatment prior to study enrollment. * Disease status must be that of measurable or nonmeasurable disease as defined by Solid Tumor Response Criteria (RECIST) * Karnofsky performance status \>70% (Eastern Cooperative Oncology Group 0-1) * Age 18 years or older * Adequate organ function within 14 days of study enrollment including the following: * Adequate bone marrow reserve: absolute neutrophil (segmented and bands) count (ANC) ≥ 1.5 x 10\^9/L, platelets ≥100 x 10\^9/L, and hemoglobin ≥ 10 g/dL * Hepatic: bilirubin \< 3 times the upper limit of normal (× ULN), aspartate transaminase (AST) \< 3 × ULN * Renal: creatinine ≤ 2.0 * Must share at least one class I HLA allele with the HLA-type SK23-CD80+ cell (class I alleles (A1, A2, B7, B8, C7)) * Meets eligibility criteria for and agrees to enroll in "MT1999- 06: Vaccination with Tetanus Toxoid and Keyhole Limpet Hemocyanin (KLH) to Assess Antigen-Specific Immune Responses" (IRB # 9904M01581, CPRC #2002LS032) * Women of childbearing potential and men whose partners are of childbearing potential are required to use an effective method of contraception (ie, a hormonal contraceptive, intrauterine device, diaphragm with spermicide, condom with spermicide, or abstinence) during the study and for 3 months after the last dose of study drug. * Voluntary written informed consent before performance of any study-related procedure not part of normal medical care, with the understanding that consent may be withdrawn by the subject at any time without prejudice to future medical care. Exclusion criteria: * History of brain metastases or positive brain scan at on-study * Immunosuppressive therapy i.e., prednisone or organ transplant patients, however topical or inhalational steroids are allowed. * Autoimmune diseases requiring immunosuppressive therapy. * History of symptomatic pulmonary disease will have pulmonary function tests (PFTs) performed. Patients with symptoms of dyspnea or rales, wheezes or rhonchi on physical exam will undergo PFTs. Those with FEV1 \<50% of predicted or corrected DLCO \<50% are not eligible. * Patients with cardiac disease such as recent myocardial infarction (\< 3 months prior), unstable angina, or heart failure requiring medical intervention will undergo cardiac evaluation. Cardiac testing may include ECG, MUGA or echocardiogram, and/or thallium stress test as indicated to evaluate cardiac risks. Those patients with exercise-induced ischemia or an ejection fraction by MUGA or echocardiogram \< 40% are not eligible. * Due to the origin of the KLH protein, patients with a history of seafood allergy are excluded from receiving KLH. * Hypersensitivity to any component of the vaccine, including Thimerosal, a mercury derivative, is a contraindication (taken from tetanus toxoid package insert). * The occurrence of any type of neurologic symptoms to tetanus vaccine in the past is a contraindication to further use (taken from tetanus toxoid package insert). * Subjects who have had tetanus toxoid within the last 7 years will not receive the tetanus vaccine component of this * Pregnant (positive pregnancy test) or lactating women. Use of LMI vaccine during pregnancy is not approved for use by the FDA during pregnancy. IL-2 is pregnancy category C - risk in pregnancy cannot be ruled out.