Trastuzumab in Combination With Vinorelbine or Taxane-Based Chemotherapy in Patients With Metastatic Breast Cancer

* All patients will receive trastuzumab then be randomized into one of two arms. Arm A: Trastuzumab in combination with weekly vinorelbine and Arm B: Trastuzumab in combination with a weekly taxane-based regimen, either paclitaxel or docetaxel, chosen at the discretion of the investigator. * Treatment is administered on an outpatient basis. Trastuzumab is administered weekly. There is a one-time loading dose for the first week of the first cycle. For that initial treatment, only, the trastuzumab dose is 4mg/kg. The dose for all subsequent weekly trastuzumab treatments is 2mg/kg. * Arm A: vinorelbine is administered every week and the dose is adjusted based on the absolute neutrophil count for that week. Vinorelbine is given after trastuzumab. * Arm B: Either paclitaxel given weekly (dose bases on absolute neutrophil count) or docetaxel given on weeks 1,2,3,5,6,7 of each 8-week cycle (dose based upon absolute neutrophil count). Patients on paclitaxel will also receive dexamethasone, diphenhydramine and ranitidine to help prevent allergic or hypersensitivity reactions. Patients on docetaxel will receive dexamethasone to help reduce fluid retention or edema. * Every 8 weeks the patients cancer will be re-evaluated to see if the treatment is working. If the treatment appears to be working, treatment will continue. Standard radiological testing (x-rays, CT scan, radioactive drug scans, or MRI's) will be used to follow the disease treatment. * Heart function will be measured after 16 weeks to be sure it is safe to continue treatment. * Every 8 weeks, patients' will be asked to complete a brief written survey that asks about symptoms and side effects. * Patients' will remain on the treatment as long as there is no disease progression or unacceptable side effects.