Inclusion Criteria:

Phase I

- Histologically proven malignancy advanced non-hematologic malignancy that is not
curable by standard surgery, radiation therapy, or chemotherapy. Patients with
melanoma, especially those with accessible tumors will be sought for this trial, but
this part of the trial will not be limited to only melanoma patients

- No available effective therapy

- Adequate performance status for the study, ECOG 0-1

- Adequate baseline organ system function,

- Agreement to use a barrier method of contraception, if potentially fertile

- Ability to understand and willingness to grant informed consent

- Patients with brain metastases are eligible only if the brain lesions are under
control for a minimum of 4 weeks, with no progressive symptoms, and off systemic
steroids. Patients with primary brain tumors are eligible if their dose of systemic
steroids is stable for at least 5 days.

- Completed prior chemotherapy a minimum of 4 weeks previously (6 weeks for BCNU and/or
mitomycin C), 4 weeks for prior biologic therapy, and 2 weeks for localized radiation
therapy. All treatment related toxicity must have resolved as well. Patients can not
receive concomitant radiation therapy

- Patients must be 18 years of age or above and competent to sign an institutionally
IRB approved informed consent Phase II Trial

- For the phase II trial, all patients must have histologically advanced and incurable
melanoma. Disease must be measurable.

- No other active malignancy including solid tumors or hematologic cancers at risk for
recurrence greater than 50% within 24 months.

- Melanoma patients can have up to 3 regimens of prior biologic therapies as adjuvant
or for disseminated disease, but only a single systemic chemotherapy regimen for
metastatic disease. Patients receiving chemotherapy in the adjuvant therapy may have
single chemotherapy regimen for advanced disease if greater than 6 months from
adjuvant therapy.

- Adequate baseline organ system function,

- Completed prior chemotherapy a minimum of 4 weeks previously (6 weeks for BCNU and/or
mitomycin C), 4 weeks for prior biologic therapy, and 2 weeks for localized radiation
therapy. No prior PS-341 is allowed. All treatment related toxicity must have
resolved as well. Patients can not receive concomitant radiation therapy

- Patients must be 18 years of age or above and competent to sign an institutionally
IRB approved informed consent.

- Patients must have documented progression over the previous 6 months by physical
exam, X-ray, CT scan or PET scan.

Exclusion Criteria:

Phase I

- Patients with Grade 2 or greater peripheral neuropathy

- Above a maximum of 320 mg/m2 of CDDP for lifetime previously administered would make
patient ineligible. No prior taxanes.

- Uncontrolled or serious infection

- New York Heart Association Class III or IV heart disease or uncontrolled angina

- Myocardial infarction, cerebrovascular accident, or pulmonary embolism within the
past 6 months

- Concurrent therapy for cancer

- Inability to comply with protocol-specified procedures Phase II Trial Component

- Patients with Grade 2 or greater peripheral neuropathy.

- Uncontrolled or serious infection

- New York Heart Association Class III or IV heart disease or uncontrolled angina

- Myocardial infarction, cerebrovascular accident, or pulmonary embolism within the
past 6 months

- Concurrent therapy for cancer

- Inability to comply with protocol-specified procedures

- Patients with brain metastases are ineligible unless the lesions have been resected,
there is no evidence of active disease and surgical resection took place a minimum of
3 months previous to enrollment.

- Above a maximum of 320 mg/m2 of CDDP for lifetime previously administered would make
patient ineligible. No prior taxanes