It depends on the data
There's nothing wrong with a search service aggregating data for statistical analysis - if they provide a service, it's fair enough to get something back for it. An example of aggregated statistical data might be something like:
Search term: "latest sci-fi films"
Age 10-18: Males 8%, Females 3%
Age 18-25: Males 14%, Females 9%
Age 25-35: Males 19%, Females 13%
From this, promoters of sci-fi films could determine that the best target demographic to punt their latest special-effects extravaganza to might be the 25-35 males group. They would then tell the search engine "Show our ads to this group" and everyone registered in that demographic would then get the ads. At no point does the advertiser or the search service know anything about who in particular searches what in the search service's customer base; and that's not an invasion of privacy.
What IS an invasion of privacy is when the data is targetable by user, like this:
Customer No. 1234567 searches:
"latest sci-fi films": 45 times
"wow fan art": 23 times
"sandra bullock images": 17 times
This kind of data is what allows "profiling"; it allows the search service to build an image of the sort of person I am and what I'm into. It doesn't matter whether it's stored as "Steve Roper" or "Customer 1234567", it's still a personal profile - and that "1234567" is no doubt an index linked to my name anyway. Now I hold that if you want to get to know me on that personal a level, you can damn well do it to my face and with me having a quid-pro-quo chance to learn about you too. Certainly it may be useful to me to have the search service store my history (which I do with Google - it's interesting to go back and see what you were searching for a year ago), but the moment they start using it to create manipulative advertising designed psychologically to exploit my weaknesses I draw the line. That's why my immediate reaction to any unsolicited advertising that addresses me by name, or appears to source information from a profile of my interests (and that's not hard to ascertain!), is never to do business with that company again, and to let them know that in no uncertain terms.
So whether this plane by the mobile companies is right or wrong depends on how they are aggregating the data. Demographics, ok. Profiling - NO.