Study of 2 Different Doses of Revlimid in Biochemically Relapse Prostate Cancer

The primary objectives of the study are: * To evaluate feasibility, safety and tolerance of 6 months administration of Revlimid at 5mg/day and 25mg/day, given orally in subjects with prostate cancer with evidence of biochemical relapse (M0) following local treatment (i.e., surgery or radiation). * To assess the rate of PSA (prostatic specific antigen) progression at 6 months after treatment with 5mg/day and 25mg/day of Revlimid (CC-5013) in patients with evidence of biochemical relapse after local therapy. The secondary objectives of the study are: * To provide preliminary assessments on the effects of Revlimid (CC-5013) at 5mg/day and 25mg/day on various PSA constructs in the subject population (i.e., PSADT \[Prostatic Specific Antigen Doubling Time\] and PSA slope) by comparing pre and post treatment patterns in each arm. * To evaluate preliminary pharmacodynamic correlations between serum revlimid concentrations and toxicity, PSA constructs and other evidence of disease progression.