See the outrage over other privacy issues in the past regarding Google, Facebook, and countless other services. Specifically, see the outrage over the Google Buzz fiasco as an example.
Privacy issues are a concern. People aren't interested in the specifics, but they make the assumption that their information is kept private.
> There are already solutions for the people who want them (stop sending referer, adblock, etc).
There were solutions for Google Buzz at the time. Just because they exist doesn't mean they are implemented in a way that people can use them easily. The problem isn't the tools, it's the ability to use those tools by default.
Let me make this clear: people assume their information is secure by default. So, the reason you don't see a bigger uproar over this is because of assumptions people make.