Inclusion Criteria

Inclusion Criteria - for Phase I

- Histologically proven malignancy (confirmed by Vanderbilt pathologists), 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 (ie; therapy known to be curative, to prolong
survival, to reduce tumor-related symptoms, or to have a tangible, beneficial effect
upon the patient)

- Adequate performance status for the study, Eastern Cooperative Oncology Group (ECOG)
0-1

- Adequate baseline organ system function, usually:

- Absolute neutrophil count > or equal to 1500/uL

- Hemoglobin > or equal to 9.0g/dL

- Platelet count > or equal to 100,000/uL

- Institutional Normalized Ratio (INR) < 1.5 prior to any invasive biopsy of tumor
tissue

- Creatinine < or equal to 1.5x institutional upper limit of normal (IULN) (this
may be adjusted for drugs totally dependent upon or independent of renal
clearance)

- Aspartate and alanine aminotransferase < or equal to 2.5x IULN, bilirubin < or
equal to 1.5x IULN

- 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
Institutional Review Board approved informed consent

Exclusion Criteria - for 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 (ie, treatment, monitoring, or
follow-up)

Inclusion Criteria - for Phase II

- For the phase II trial, all patients must have advanced and incurable melanoma.
Disease must be measurable. Histologic proof of disease past the primary site

- No other active malignancy including solid tumors or hematologic cancers within 24
months other than CIS, non-melanoma skin cancer, DCIS of breast, and melanoma in situ

- Melanoma patients can have up to 2 regimens of prior biologic therapies and a single
regimen of systemic chemotherapy for disseminated disease.. Chemotherapy is allowed
only in the chemotherapy treated patients cohort. Prior TMZ or DTIC is only allowed
in those patients enrolled into the prior chemotherapy cohort

- All patients must have ECOG 0-1.

- Adequate baseline organ system function, usually:

- Absolute neutrophil count > or equal to 1500/uL

- Hemoglobin > or equal to 9.0g/dL

- Platelet count > equal to 100,000/uL

- INR < 1.5 prior to any invasive biopsy of tumor tissue

- Creatinine < or equal to 1.5x institutional upper limit of normal (IULN) (this
may be adjusted for drugs totally dependent upon or independent of renal
clearance)

- Aspartate and alanine aminotransferase < or equal to 2.5x IULN, bilirubin < or
equal to 1.5x IULN

- 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. Prior TMZ
or DTIC is only allowed in those patients enrolled into the prior chemotherapy cohort

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

Exclusion criteria - for Phase II

- Patients with Grade 2 or greater peripheral neuropathy.

- Uncontrolled or serious infection requiring parenteral antibiotics

- 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 xiii. Inability to comply with protocol-specified
procedures (ie, treatment, monitoring, or follow-up)

- Patients with brain metastases are ineligible unless the lesions have been resected
or irradiated a minimum of 2 months prior to treatment, be off of steroids, and show
no evidence for active disease on MRI,

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