My personal view is that "you can't have your cake and eat it too." Part of the reason Google is the best at search and targeted ads is because of their data mining. Yes, it can be called an invasion of privacy (and rightly so), but Google could not have become as accurate and precise as they are without it. There is a reason "Google" has become a verb, but "Bing" and "Yahoo" and "Ask" have not. I personally have no problem with the data retention and use, but I certainly understand if someone does. To me, it's worth it to have the convenience of Google's services. To others, it isn't. Pick your poison.
I agree with CrackberryBrandon that Apple has the right idea with using the data but disassociating it with the user. It might be a compromise that will give consumers the feeling that their privacy is considered.