Inclusion Criteria:

- must have histological or cytological diagnosis of cutaneous melanoma and clinical
evidence of metastatic, non-resectable regional lymphatic, or extensive in transit
recurrent disease. Patients who have had resected metastases will also be eligible
provided they have measurable disease.

- have measurable disease. Measurable disease is defined as the presence of at least
one measurable lesion.

- ECOG performance status ≤ 2 (Karnofsky ≥ 60%).

- Female subjects must be either surgically sterilized or willing to use an acceptable
method of birth control (ie, a hormonal contraceptive, intra-uterine device,
diaphragm with spermicide, condom with spermicide, or abstinence) for the duration of
the study. Male subjects must agree to use an acceptable method for contraception for
the duration of the study.

- Patients must have normal organ and marrow function.

- Prior Therapy: Patients with an ECOG performance status of ≤ 2 will be eligible for
this protocol regardless of the number of prior treatments provided they have
recovered from the reversible effects of prior therapy. Patients are permitted to
have received therapy with adjuvant IFN-α2b, if it was completed > 6 months prior to
enrollment in the current study.

- Patients with brain metastases are eligible for entry into the study, but must have
received definitive therapy consisting of external beam radiation therapy, gamma
knife therapy or surgical resection and be clinically stable. Four weeks after the
definitive therapy is completed, repeat MRI or CT scans must demonstrate
stabilization of disease, and there must be no requirement for Decadron. If the
patient does not have brain metastases, then only one brain CT or MRI is required
prior to enrollment on study.

Exclusion Criteria:

- Patients meeting any of the following exclusion criteria are not to be enrolled in
the study.

- Patient has a platelet count of < 100 × 109/L within 14 days before enrollment.

- Patient has an absolute neutrophil count of < 1.0 x 109/L within 14 days before
enrollment.

- Patient has a calculated or measured creatinine clearance of < 30 mL/minute within 14
days before enrollment.

- Patient has history of significant brain metastases or other clinically significant
central nervous system disease.

- Patient has ≥Grade 2 peripheral neuropathy within 14 days before enrollment.

- Patient has hypersensitivity to bortezomib, boron or mannitol.

- Patients with evidence of proteinuria on urinalysis.

- Female subject is pregnant or breast-feeding.

- Received other investigational drugs with 14 days before enrollment.

- Serious medical or psychiatric illness likely to interfere with participation in this
clinical study.

- History of serious psychiatric illness that might be exacerbated by IFN-α-2b.