I'll sort of cheat and neglect the relativity part--instead, I'm going to focus on your mathematical confusion regarding differentiation.
What you've forgotten is that we have a constraint. Your argument is thus, right:
$$\text{if } \vec v_{b}=\vec v_{a}+\vec v_{b,a}, \text{ then } \vec a_{b}=\vec a_{a}+\vec a_{b,a} \text{ by differentiation}$$
Where $b$ and $a$ are frames of reference, and $b,a$ denotes the acceleration/velocity of the frames relative to each other.
Aah, but we have a constraint: $\vec F=\frac{\rm d\vec p}{\rm d t}=m\frac{\rm d\vec v}{\rm d t}=m\vec{a} _\text{ (for constant mass)}$.
This constraint makes little difference when we switch between frames with constant relative velocities, since the derivative of velocity stays the same. But, the moment we try to switch to an accelerating frame, things get icky. We get:
$$m\vec a_{b}=m\vec a_{a}+m\vec a_{b,a}\implies \vec F_b=\vec F_a+m\vec a_{b,a}$$
Looks OK, doesn't it? We could write $m\vec a_{b,a}\to\vec F_{b,a}$, and the equation would be handy-dandy--it would show that force is relative as well. Right?
Wrong. By our assumption, acceleration and velocity are relative quantities. To measure a relative quantity, one must have a reference frame. In contrast, force is something you can measure without needing a frame-- A spring balance suffices.
This equation shows that apparent force varies with your reference frame. You probably know this, but this comes from the presence of a "psuedoforce"--the $m_{b,a}$ term. It's not a real force, but it appears whenever we try to apply Newton's laws to a noninertial{*} frame. Since it's part of the apparent force, it can be measured. Since it crops up when you change frames, you will always be able to detect that a frame change occurred. This is in contrast to switching between inertial frames--unless you have a fixed object outside, you can't tell the difference.
So basically, it's not a methematical issue but an issue with what can and can't be measured inside a frame
Actually, all of this comes from the fact that Newton's laws are only applicable in an inertial frame. When asked "which of Newton's laws is the most important?" most people would say the second and/or third law. The first law is always counted as a result of the second law. This is actually false-there is no privileged law of the three-- and they are independant. The function of the first law is to define the realm of applicability of the three. In a noninertial frame, the first law does not hold(since an object at rest still gets accelerated), so the other two do not hold either. The pseudoforce is just a way of cheating the laws into working.
So, if we have a bunch of laws that only work in a non-accelerating frame, that means that "non-accelerating" has an absolute meaning. Thus all acceleration is absolute.
In short: the "relativeness" was not there in the first place. It just appears when we take a special case of $a_{frame}=0$--useful in itself, but not generalisable.
* inertial-->constant velocity no gravity, noninertial-->acceleration and/or gravity