Inclusion Criteria:

- AML, ALL, or high-risk MDS (R-AEB or RAEB-t) that has:

- Not responded (no CR) to initial induction chemotherapy, or

- Recurred after an initial CR of < 1 year, or

- Recurred after an initial CR of > 1 year and failed to respond to an initial
re-induction attempt, or

- Recurred more than once, OR

- Chronic myeloid leukemia in myeloid blast phase

- Patients with CML blast phase may receive PS-341 as their first therapy for
blast phase or after failing other treatments for blast phase

- Patients with refractory or relapsed acute promyelocytic leukemia are eligible
provided they have failed an ATRA-containing regimen

- Patients who are likely to benefit from allogeneic bone marrow transplantation (i.e.,
age < 60 years of physiological age with histocompatible donor) should be excluded
from this study unless such therapy is not feasible

- ECOG performance status =< 52 (Karnofsky >= 50%)

- Total bilirubin < 1.6 mg/ml

- ALT or AST =< 2.5 times the institutional upper limit of normal

- Creatinine < 1.6 mg/ml or creatinine clearance >= 60 mL/min/1.73 m^2 for patients
with creatinine levels above institutional normal

- Patients must have been off chemotherapy for 2 weeks prior to entering this study and
recovered from the toxic effects of that therapy; use of hydroxyurea on patients with
rapidly proliferative disease (i.e., absolute peripheral blood blast count >= 5 x
10^9/L, and increasing by >= 1 x 10^9/L/24 hrs) is allowed up to 24 hours prior to
the start of therapy with PS-341

- The effects of PS-341 on the developing human fetus at the recommended therapeutic
dose are unknown; for this reason, women of childbearing potential and men must agree
to use adequate contraception (hormonal or barrier method of birth control) prior to
study entry and for the duration of study participation; should a woman become
pregnant or suspect she is pregnant while participating in this study, she should
inform her treating physician immediately

- Because the potential risk of toxicity in nursing infants secondary to PS-341
treatment of the mother is unknown but may be harmful, breastfeeding should be
discontinued if the mother is treated with PS-341

- Ability to understand and the willingness to sign a written informed consent document

Exclusion Criteria:

- Patients undergoing therapy with other investigational agents

- Patients with known brain metastases or CNS disease should be excluded from this
clinical trail because of their poor prognosis and because they often develop
progressive neurologic dysfunction that would confound the evaluation of neurologic
and other toxicities

- Uncontrolled intercurrent illness including, but not limited to ongoing or active
infection, symptomatic congestive heart failure, or unstable angina pectoris, or
cardiac arrhythmia

- HIV-positive patients receiving, anti-retroviral thearpy (HAART) are excluded from
the study because of possible pharmacokinetic interactions; appropriate studies will
be undertaken in patients receiving, HAART therapy when indicated