This particular experiment is getting scrutiny because they published the results in a journal and it is a rather egregious example (the hypothesis, and test methodology, both demonstrate a particular brand of recklessness you don't tend to see in website A/B testing.)
EDIT: For reference, I know a lot about this subject because I worked extensively at IMVU, one of the first consumer-facing websites to aggressively A/B test almost everything. I don't have a luddite perspective on this.
I have no problem claiming that this is usually unethical.
Changing a product you provide to a customer is often fine, though there could be contract or consumer-protection law or other legalities to consider. This may be true even when your product is free ("see a lawyer"). So changing your website and trying it on a handful of your audience first is also fine. Assuming no legal issues, there is a general understanding that fixes and improvements happen, and that the client can choose not to participate at any time, so that situation is probably fine as well.
Also intent counts for a lot - "trying to find a better search tool" or other technical features are clear in what they are intending to accomplish: bugfixes and/or new features.
The problem starts when you are trying to experiment on people directly, where the entire goal of the project is to poke at people and see how they react. After seeing how that kind of activity can end up in WW2, we decided it was a far better idea to put some precautions in place. It's annoying (and makes medical testing MUCH more expensive), but this is one of those situations where it's better to be overly cautious.
What I don't understand about FB is that - compared to experiments with SERIOUS risk such as drug testing - the experiment was rather benign. It shouldn't have been very difficult to get a proper IRB stamp of approval. The informed consent part could (I suspect) have been handled with some web page with an overview of the experiment and an opt-in button.
(and no, opt-in wouldn't have affected the test if you do you statistics correctly and are careful in your language on the opt-in page)
Failure to do this relatively easy steps is unprofessional at best, and highly suspicious at worst. Acting like human experimentation is not even worth of such protections makes me wonder what kind of person the experimenter is (stupid? or just badly narcissistic?).
Actually doing such an experiment without the subject consent supplies the answer: the experimenter is both stupid and dangerously narcissistic.
The dividing line, is largely: are you trying to do things to people behind their back? Or are you including them in the decision to participate (or not participate)?
For more specific details, see your local ethics committee.