Inclusion Criteria:

- Signed informed consent.

- Histologic demonstration of adenocarcinoma of the prostate. Patients with variant
histologies (ductal carcinoma, small cell carcinoma) are eligible only for the Phase
I part of the trial, but are excluded from the Phase II. If no sample of the
primary tumor was obtained, biopsy of a metastatic site is sufficient if the tissue
stains positive for PSA. Some pathologic material must be available for review.
Indicator need not be biopsy proven if the clinical presentation is characteristic.

- Androgen-Independent progression of prostate carcinoma, as shown by:

1. Serum testosterone level of < 50 ng/dL or prior bilateral orchiectomy. Treatment
to maintain castrate levels of testosterone (LHRH agonists) should continue, and

2. Either symptomatic progression, or, if patient is asymptomatic, then a rising
serum PSA in two occasions at least 1 week apart, with a minimum pre-treatment
serum PSA of 5.

- Patients must be off anti-androgens, such as flutamide (Eulexin), bicalutamide
(Casodex) or nilutamide (Nilandron). They must have no evidence of response at least
4 weeks (6 weeks for bicalutamide) since anti-androgen withdrawal (or progression at
any time since anti-androgen withdrawal).

- Patients with nodal and/or visceral disease are eligible.

- Patients may have up to 2 prior chemotherapy regimens for prostate cancer, provided
that more than 3 weeks have elapsed since the last treatment and patients have
recovered from toxicity. Ketoconazole is considered chemotherapy. Prior Taxanes are
allowed in both the Phase I and Phase II part of the trial. For the Phase II part
of the study, patients must have progressed after >/= 1 and regimens for prostate cancer (as neoadjuvant treatment or for metastatic disease).

- Up to one prior dose of Strontium-89 (Metastron) is allowed, if given more than 12
weeks prior to study entry. Patients may have had radiation therapy involving < 15%
of the bone marrow (completed more than 3 weeks of initiation of the study).

- Previous treatment with PC-SPES, herbal / alternative medicines, anti-angiogenesis
inhibitors, immunotherapy, or other non-androgen mediated pathways (such as epidermal
growth factor receptor antagonists or farnesyl transferase inhibitors) is allowed,
provided that there is unequivocal evidence of disease progression since completion
of the therapy and more than 2 weeks have elapsed since last treatment.

- Patients must be at least 2 weeks from prior surgery.

- Adequate physiologic reserve as evidenced by:

1. Life expectancy of at least 12 weeks

2. Zubrod performance status of < 2.

3. Age > 18 years old.

4. No clinical history of heart disease and a normal elect electrocardiogram (EKG
or ECG), OR an ejection fraction of at least 45% (by echocardiogram (ECHO),
Multiple Gated Acquisition (MUGA) or ventriculography).

5. serum glutamic pyruvic transaminase (SGOT/SGPT) and conjugated bilirubin less
than twice the upper limit of normal.

6. Serum creatinine < 2.0 mg/dl (or, if creatinine > 2 mg/dl, then a creatinine
clearance of at least 35 ml/min (measured or estimated by the Cockcroft formula:
CLcr= [(140-age) * weight (kg)] / [72 * serum creatinine (mg/dl)].

7. Absolute neutrophil count (ANC)>1500/mm^3; Platelets >100,000/mm^3; hemoglobin >
9.0 gm/dl.

Exclusion Criteria:

- Patients with variant histologies (ductal or small cell carcinoma) are excluded from
the phase II part of the trial (are eligible for the phase I part).

- Patients with no prior chemotherapy for prostate cancer are excluded from the phase
II part of the study.

- Patients with central nervous system (CNS) metastases or serious medical illnesses,
active or uncontrolled infections, significant psychiatric disorders that preclude
giving informed consent, patients with NCI grade > 2 peripheral neuropathy or
patients with a history of another malignancy (except from superficial bladder cancer
or basal cell carcinoma of the skin) within 5 years prior to study entry are excluded
from the trial.