Study of Patients With Stage IV Malignant Melanoma Using PS-341 (Bortezomib, Velcade) and Interferon-alpha-2b in Malignant Melanoma

The primary objective of this study is to: • Determine the safety, tolerability and DLTs of VELCADE when administered in combination with interferon-alpha-2b (IFN-α-2b) to patients with metastatic malignant melanoma. The secondary objectives of this study are to: * Document any objective anti-tumor responses that may occur in response to this treatment regimen. * Document the time to tumor progression in patients receiving this treatment regimen. * Measure levels of the cell cycle proteins p21 and p27 in PBMCs and tumor biopsies obtained pre-study and during week 4 of Cycle 1 (Day 26). * Conduct histologic evaluations of microvessel density, tumor apoptosis and lymphocytic infiltrates within tumor biopsies obtained pre- and post-study. * Measure plasma levels of bFGF and VEGF over the course of the study. * Monitor the effects of proteasome inhibition on the biological activity of IFN-α within immune cells by measuring Jak-STAT signal transduction in patient PBMCs.