Inclusion Criteria

- INCLUSION CRITERIA:

A. Histologically confirmed carcinoma that for patients in the first two arms (colorectal
and non-colorectal cancer) is CEA or MUC-1 positive. Tumor that has been shown to express
CEA or MUC-1 (greater than or equal to 20 % of cells) by immunohistochemical techniques or
patients that have had an elevated serum CEA (greater than 5 microgram/L) at any point
during their disease course. For patients in the ovarian and breast cancer arms, as
greater than 95% of these express MUC-1 or CEA, we will not require staining prior to
coming onto trial.

B. Patients must have completed at least one 5-FU containing chemotherapy regimen (e.g.
5-FU/LV with or without either irinotecan or oxaliplatin) for the colorectal cancer arm,
or either failed or not be a candidate for therapy of proven efficacy for their disease in
the non-colorectal, breast, and ovarian cancer arms.

C. 18 years of age or greater.

D. All patients on the colorectal adenocarcinoma cohort must be HLA-A2 positive.

E. At least 10 patients on the non-colorectal adenocarcinoma cohort must be HLA-A2
positive.

F. Patients on the breast and ovarian arms are not required to be HLA-A2 positive.

G. For the colorectal and non-colorectal cancer arms (the initial two arms), patients will
be required to have: metastatic disease (measurable or evaluable), metastatic disease
documented by biopsy but not evaluable by imaging (e.g. small volume peritoneal disease),
and patients with surgically resected metastatic disease at high risk of relapse. For the
ovarian and breast cancer arms, patients will be required to have evaluable disease.

H. Able to understand and give informed consent.

I. Able to avoid close household contact (close household contacts are those who share
housing or have close physical contact) for at least three weeks after recombinant
vaccinia vaccination with persons with active or a history of eczema or other eczematoid
skin disorders; those with other acute, chronic or exfoliative skin conditions (e.g.,
atopic dermatitis, burns, impetigo, varicella zoster, severe acne, or other open rashes or
wounds) until condition resolves; pregnant or nursing women; children 3 years of age and
under; and immunodeficient or immunosuppressed persons (by disease or therapy), including
HIV infection.

J. ECOG performance status of 0 - 1.

K. Serum creatinine not above the institution limits of normal, and AST less than or
equal to twice the upper limits of normal OR creatinine clearance on a 24 hour urine
collection of greater than or equal to 60 mL/min.

L. Total bilirubin within the institution limits of normal OR patients with Gilbert's
syndrome, a total bilirubin less than or equal to 3.0

M. Recovered completely from any reversible toxicity associated with recent therapy.
Typically this is 3-4 weeks for patients who most recently received cytotoxic therapy
except for the nitrosoureas and mitomycin C for which 6 weeks is needed for recovery.

N. Hematological eligibility parameters (within 16 days of starting therapy):

- Granulocyte count greater than or equal to 1,500/mm3

- Platelet count greater than or equal to 100,000/mm3

- Hgb greater than or equal to 10 Gm/dL

O. Prior immune therapy with related vaccinia and fowlpox vaccines or antigen-specific
peptides is allowed.

P. Men and women must agree to use effective birth control or abstinence during and for a
period of 4 months after the last vaccination therapy.

Q. Patients with prostate cancer must continue to receive GnRH agonist therapy (unless
orchiectomy has been done).

R. Patients should appear clinically stable (in the opinion of the prinicipal
investigator) to complete the full 3 month course of vaccination with an anticipated
survival of 6 months or longer.

INCLUSION CRITERIA FOR EXTENSION OR MAINTENANCE PHASE:

A. Completion of Core phase of the protocol.

B. Stable or responding disease (PR, CR).

C. No dose limiting toxicity (see below) in Core phase possibly, probably or definitely
related to the vaccine.

Dose limiting toxicities include:

- Any Grade 2 generalized urticaria or Grade 3 or greater allergic reaction.

- Any Grade 2 or greater autoimmune response.

- Any Grade 3 or greater hematologic or non-hematologic reaction, including
injection-site reaction.

EXCLUSION CRITERIA:

A. Patients should have no evidence of being immunocompromised as listed below.

- Human immunodeficiency virus positivity due to the potential for decreased tolerance
and risk for severe side effects

- Active autoimmune diseases requiring treatment or a history of autoimmune disease
that might be stimulated by vaccine treatment. This requirement is due to the
potential risks of exacerbating autoimmunity. Patients with endocrine disease that is
controlled by replacement therapy including thyroid disease and adrenal disease and
vitiligo may be enrolled.

B. Concurrent use of systemic steroids, except for physiologic doses for systemic steroid
replacement or local (topical, nasal, or inhaled) steroid use. Limited doses systemic
steroids to prevent IV contrast, allergic reaction, or anaphylaxis (in patients who have
known contrast allergies) are allowed.

C. History of allergy or untoward reaction to prior vaccination with vaccinia virus.

D. Pregnant or breast-feeding women.

E. Altered immune function, including immunodeficiency or history of immunodeficiency;
eczema; history of eczema, or other eczematoid skin disorders; or those with acute,
chronic or exfoliative skin conditions (e.g. atopic dermatitis, burns, impetigo, varicella
zoster, severe acne, or other open rashes or wounds).

F. Serious intercurrent medical illness which would interfere with the ability of the
patient to carry out the treatment program, including, but not limited to, inflammatory
bowel disease, Crohn's disease, ulcerative colitis, or active diverticulitis

G. Patients with a history of cardiomyopathy or symptomatic congestive heart failure
(unless stable on treatment), symptomatic arrhythmia not controlled by medication.
Unstable atherosclerotic heart disease (e.g. unstable angina) who require active
intervention and history of myocardial infarction or embolic stroke within the past 6
months.

H. Clinically active brain metastasis, or a history of encephalitis, multiple sclerosis,
or seizures within the last year (from seizure disorder or brain metastasis).

I. Medical conditions, which, in the opinion of the investigators would jeopardize the
patient or the integrity of the data obtained.

J. Concurrent chemotherapy; an exception to this is to allow for patients with breast
cancer who are receiving trastuzumab, to continue therapy with trastuzumab while receiving
the vaccine treatment.

K. Serious hypersensitivity reaction to egg products.

L. Clinically significant cardiomyopathy requiring treatment.

M. Chronic hepatitis infection, including B and C, because of potential immune
impairment.

N. Although topical steroids are allowed, steroid eye drop are contraindicated.

O. Cardiac complications, including recent myocardial infarction or cerebrovascular
accident within one year, and/or unstable or uncontrolled angina.