Inclusion Criteria:

- Histologically or cytologically confirmed metastatic malignant melanoma

- Measurable disease defined as at least one lesion whose longest diameter can be
accurately measured as >= 2.0 cm

- Absolute neutrophil count (ANC) >= 1500/uL

- PLT >= 100,000/uL

- Total bilirubin =< 2.5 x institutional upper normal limit (UNL)

- AST =< 2.5 x UNL

- Creatinine =< 1.5 x UNL or calculated creatinine clearance > 60 mL/min/1.73 m^2 for
patients with creatinine levels > 1.5 x UNL using the Cockcroft-Gault formula

- Life expectancy of >= 3 months

- ECOG performance status 0 or 1

- Capable of understanding the investigational nature, potential risks and benefits of
the study and willing to sign the written informed consent document

Exclusion Criteria:

- Any of the following:

- Any prior chemotherapy

- Immunotherapy =< 4 weeks prior to study entry

- Biologic therapy =< 4 weeks prior to study entry

- Radiation therapy =< 4 weeks prior to study entry

- Failure to fully recover from adverse effects of prior therapies regardless of
interval since last treatment

- Other concurrent chemotherapy, immunotherapy, radiotherapy, or any other therapy
or supportive care considered investigational

- Known brain metastases requiring active treatment; NOTE: these patients are excluded
from this clinical trial because of their poor prognosis and because they often
develop progressive neurologic dysfunction that would confound the evaluation of
neurologic and other adverse events

- History of allergic reactions attributed to compounds of similar chemical or biologic
composition to PS-341

- Uncontrolled intercurrent illness including, but not limited to:

- Ongoing or active infection

- Symptomatic congestive heart failure

- Unstable angina pectoris, cardiac arrhythmia

- Psychiatric illness that would limit compliance with study requirements

- HIV-positive patients receiving combination anti-retroviral therapy; NOTE: patients
with immune deficiency are at increased risk of lethal infections when treated with
marrow-suppressive therapy; these patients are excluded from the study because of
possible pharmacokinetic interactions with PS-341; appropriate studies will be
undertaken in patients receiving combination antiretroviral therapy when indicated

- Any of the following:

- Pregnant women

- Nursing women

- Men or women of childbearing potential who are unwilling to employ adequate
contraception (condoms, diaphragm, birth control pills, injections, subcutaneous
implants, intrauterine device [IUD], abstinence, etc.)

- NOTE: this study involves an investigational agent whose genotoxic, mutagenic
and teratogenic effects on the developing fetus and newborn are unknown

- Only non-measurable disease, including lesions not clearly measurable in one
dimension, small lesions (longest diameter < 20 mm), and truly non-measurable
lesions, which include the following as per RECIST criteria:

- Bone lesions

- Leptomeningeal disease

- Ascites

- Pleural/pericardial effusion

- Inflammatory breast disease

- Lymphangitis cutis/pulmonis

- Abdominal masses that are not confirmed and followed by imaging techniques

- Cystic lesions