Primary Objective:

-Establish the dose-limiting toxicity (DLT) and maximum tolerated dose (MTD) of weekly mitoxantrone in combination with weekly PS-341 in patients with advanced AI-PCa.

Secondary objectives:

• Evaluate the effect of bortezomib and mitoxantrone in combination on PSA levels among patients with baseline PSA levels >/=5 ng/mL who are treated near the maximum tolerated dose.
• Monitor the effect of escalating doses of bortezomib combined with mitoxantrone on selected parameters of clinical benefit (i.e. performance status, tumor-related symptoms, measurable disease response).

Mitoxantrone is used to treat bone pain in advanced prostate cancer and inhibits many proteins that the cancer cells need to multiply.

Bortezomib is a member of a new class of drugs that possess powerful and broad-spectrum anti-tumor activity and inhibit many proteins that the cancer cells need to survive and multiply.

Pre-study testing will include brief physical examination, vital signs (weight, height, temperature, pulse, respiratory and blood pressure), chest x-ray, EKG (test to measure the electrical activity of the heart), echocardiogram, blood test, urine tests, and depending on the stage of the disease, a CT scan and/or bone scan.

During treatment, the participants will receive one dose of Mitoxantrone combined with one dose of Bortezomib every week for 4 weeks in a row followed by 2 weeks of rest; this is called a course. If side effects are not too severe, Mitoxantrone and Bortezomib will be infused rapidly into a vein while participants will be receiving normal saline ("salt in water solution") at a rate of 100ml/hour. They will receive the salt solution the entire time they are in the treatment area.

Participants will have their vital signs (temperature, pulse, breathing, blood pressure) taken before and one hour after treatment. All side effects during course one will be reviewed and, if no serious side effects took place, the participant may have additional courses. A pill may be given by mouth every day to decrease the risk of clot formation or a pill for diarrhea, nausea, and/or vomiting if the doctor believes that participants may need it.

Also during treatment, participants will have a complete physical examination by a physician or their designated representative (such as a nurse or physician assistant) each week of treatment. Bone Scan and/or CT Scan will be done if necessary. Participants will have blood tests done every week during study. A special blood test, called the 20S proteosome, will be done weekly during Cycles 1 and 2 to evaluate the activity of the drugs. Blood will be collected before you receive treatment and then at 1-2 hours afterward. About 2 teaspoons of blood will be collected each time for this. Bone scan, chest x-ray and/or CT scans will be repeated during the study every other course.

Participants will be taken off study if the disease gets worse or intolerable side effects occur. Side effects that are thought to be related to the study drug are renal failure resulting in death, and a grade 3 rash requiring treatment with steroids that recurred with subsequent treatments.

The maximum amount of time that participants can remain on the study is 8 courses of treatment. Long term follow-up of participants will include a phone call every 6 months.

This is an investigational study. Bortezomib has been approved by the FDA for investigational use only. Mitoxantrone has been approved by the FDA for treatment of symptoms in advanced prostate cancer. Only Mitoxantrone is commercially available. About 42 participants will take part in this study. All will be enrolled at M.D. Anderson .

Inclusion Criteria:

1. Patient has given voluntary written informed consent before performance of any study-related procedure not part of standard medical care.
2. Patient has histologically-confirmed advanced and/or metastatic AI-PCa requiring anti-neoplastic treatment. Patients should continue on LHRH analog therapy throughout the study period, if this is their mode of androgen suppression therapy. Patients should have discontinued anti-androgen therapy for >/= than 4 weeks (for flutamide) or >/= 6 weeks (for bicalutamide and nilutamide).
3. Patient has progressive measurable or evaluable disease, defined as meeting at least one of the three criteria, described in protocol section 4.1.
4. Zubrod performance status of </= 2 (Appendix B).
5. Resting Left Ventricular Ejection Fraction (LEVF) >/= 50%.
6. Patient has all of the following pretreatment laboratory data within 14 days (except for serum testosterone which may be done within 28 days prior to registration) before the first study drug dose: Absolute neutrophil count (ANC) >/= 1,500/mm^3. Platelets >/= 100,000/mm^3. Hemoglobin >8.0 g/dL. Total bilirubin </=1.5 x the upper limit of normal (ULN). ALT or AST </= 2.5 x the ULN, or, if the patient has liver metastases, </= 5 x the ULN. Creatinine </= 2 mg/dL. Serum testosterone </= 50 ng/mL.

Exclusion Criteria:

1. Patient has received chemotherapy (including thalidomide or ketoconazole) within four weeks, nitrosoureas within six weeks, or antibody therapy within eight weeks of enrollment.
2. Patient has received radiation therapy or Samarium-153 within four weeks of enrollment, or Strontium-89 within 12 weeks of enrollment.
3. Patient has not recovered from all serious toxic effects of previous chemotherapy or radiation or antibody therapy.
4. Patient received treatment with flutamide within four weeks of enrollment or nilutamide or bicalutamide within six weeks of enrollment.
5. Patient has had any major surgery within four weeks of enrollment.
6. Patient has a history of allergic reactions to anti-diarrheal medications or anti-emetics suggested to be administered in conjunction with study drug (see Section 5.1.4.1).
7. Patient has a history of severe hypersensitivity reaction to mitoxantrone or other agents formulated with polysorbate 80.
8. Patients with significant atherosclerotic disease, as defined by: a) myocardial infarction within six months of enrollment, uncontrolled / unstable angina pectoris or electrocardiographic evidence of acute ischemia b) clinically significant ventricular arrhythmias, c) symptomatic congestive heart failure d) significant conduction abnormalities: 2nd or 3rd degree AV blocks, bifascicular block (defined as Left Anterior Hemiblock in the presence of Right Bundle Branch Block), e) claudication limiting activity and f) history of cerebrovascular events within the last year (including TIA)
9. Patients who have received > equivalent to 180 mg/m^2 of Doxorubicin cumulative dose.
10. Patients with diabetes mellitus requiring insulin, or those that have required pharmacologic intervention for diabetes mellitus for greater than 5 years
11. Patient has uncontrolled brain metastases or central nervous system disease.
12. Patient has >/= Grade 2 peripheral neuropathy (per NCI CTC v.2).
13. Patient has an uncontrolled intercurrent illness (e.g., active infection).
14. Patient has another serious medical or psychiatric illness that could, in the investigator's opinion, potentially interfere with the patient's ability to provide informed consent or with the completion of treatment according to this protocol.