The combination of Gemcitabine and Cisplatin is one commonly used treatment that has been shown to make some patients with transitional cell cancer live longer. This study is being done to see if adding Avastin will delay the growth of the cancer and allow patients to live longer. All three drugs are given intravenously. Treatment will be given for as long as the cancer is responding and there are no severe side effects from the drugs. One group will get the standard chemotherapy with Avastin and the other group will get standard chemotherapy with a look alike intravenous infusion (placebo).