It's impossible to do anything meaningful without infringing on some overly broad (and probably invalid if challenged) patent. Any successful startup is likely to have to deal wtih patent licencing or litigation sooner or later... hopefully later when you have the resources to settle or fight.
Patents are generally held up as an enabler for small startups, but I am not so sure of that. When relatively broad and trivial ideas can be patented they can become an insurpassable barrier to entry against anyone trying to challenge the established players. As is evident in this case, they can also be weapons for use in wars between the large companies. I am working with a company now that has enjoyed a protected market niche for a long time due to patent protection, but during that time they have effectively stopped innovating. Right now I am trying to get them to go back into a mode where they are willing to take risks.
I acknowledge that patent protection is needed, but I think that we need to be much more aggressive about limiting it.