I've thought more about why Mach worried over Newton's bucket, and I understand it better now: Mach took Galileo seriously.
Galileo really laid down most of the intellectual foundations for Special Relativity. I'm not trying to take anything away from Einstein there; the fact that he actually found a way to add something to Galileo's work is pretty damn impressive. Anyway, if you take those foundations seriously, then the idea of absolute acceleration should bother you. For linear motion, we can't really know for sure if we are falling toward the earth or the earth is falling toward us. Or, more accurately, we cannot use purely local measurements to determine who is at rest and who is accelerating. We are not stopped from attributing causes to motions (e.g. we could notice that we are feeling the attraction of a giant rock below us, while the earth is only feeling the attraction of a miniscule flesh bag filled with water, or we could notice that the train has an engine in it while the earth has no engine attached to it), but even if we conceptually think of things "really" moving and "really" standing still, we need laws of physics that make no such distinction. The fundamental equations of physics have to work equally well if I assume that the train is moving or that the ground is moving, even if there is no law of physics to prohibit an intelligent physicist from asking "Well, which object has a fuel source?"
So, for linear motion the idea of absolute acceleration is clearly problematic. Galileo surely knew that, even if he dwelt more on relative velocity than relative acceleration. If we take that notion seriously, we should be a bit bothered when Isaac Newton comes along with a spinning bucket and declares "I know for certain that this is really accelerating." I mean, it's obviously true--Newton put his hands on the bucket and set it in motion; he didn't apply a large enough force to change the earth's spin--but a person who has read enough Galileo should worry about whether it's a statement that we can fit into the framework of the laws of physics.
There are a few reasons why the modern observer might not be as bothered as Mach:
1) Inertial and non-inertial frames are different. Hence special relativity is studied by sophomores while general relativity requires a whole lot of differential geometry background.
This is also true, but it was not yet clear just how different inertial and non-inertial frames are. In fact, answering Mach's challenge on that point was one of Einstein's key motivations.
2) In a uniformly accelerated reference frame there is no special point in space. In a rotating reference frame, there is an axis of rotation, relative to which no observer changes his distance. That's clearly a broken symmetry.
Again, I agree, but Noether's Theorem was not yet in the toolkit of practicing physicists. Lagrangian mechanics certainly made it apparent that symmetry was important, but the full significance of symmetry was not yet manifest. If you just look at the Euler-Lagrange equations you can immediately see that some coordinates are ignorable and thus lead to conserved quantities, but Noether proved that you don't just have to limit your analysis to obvious coordinates--any symmetry transformation that leaves the Lagrangian invariant (a notion that's a bit more subtle than just picking a coordinate system and doing the algebraic gymnastics to rewrite variables) also gives us a conserved quantity.
My conclusion is that Mach was asking the right questions. I do wish that he had left out the part about "fixed stars" (Halley had dispelled that notion) but his basic program was a sound one. He wanted to know how it was that the bucket constitutes a valid example of absolute acceleration when Galileo had taught us to be skeptical to our core when somebody says that they can measure absolutes related to motion. And, sure enough, Einstein showed that there is no fundamental way of distinguishing between acceleration and gravity, just as there is no way to tell if my car is moving and the ground is standing still or vice-versa. Mach pushed hard on the right question, and Einstein was right to revere him.