Apparently Google made a BIG mistake. Although Google released news about its upcoming Gmail service on March 31, 2004 (link), Google didn't actually file a U.S. Trademark application for the term until April 7, 2004. This put Google as the fourth entity in line filing for that term. In a system that's first-come first-serve, this could pose a substantial problem for the burgeoning e-mail enterprise.
(Internetnews.com article here and Phosita article here.)
Honestly, I wonder how this could possibly have happened. Fer cryin out loud, Google must have a bevy of beautific bodacious blood-thirsty bonsai-growing
Don't forget, Google has run afoul of legitimate preexisting uses before with Google & Froogle. Ugh-oogle! [Minus one point for a genuinely horrible pun.]
Addendum: A clarification as the March 31st date is slightly inaccurate. News was leaked on the 31st while the Official Google Press Release was issued on April 1. (Odd choice of dates, there.)