Essentially you are asking to raise the rotation matrix to an arbitrary power. To do this you can use the fact that $X^a=\exp(a \log X)$ for any matrix $X$. To compute the matrix logarithm we use
$$\log X = \log (I - (I-X)) = -\sum_{n=1}^\infty \frac{(I-X)^n}{n}$$
Now if you can diagonalize $I-X$ (perhaps there is a proof that this is always possible for $X$ a rotation matrix?) to give $I-X=SDS^{-1}$ then you have
$$\log X = -S \left(\sum_{n=1}^\infty \frac{D^n}{n}\right) S^{-1}$$
which is fast to compute (again you'd need a proof that this converges when $X$ is a rotation matrix). Now you compute the matrix exponential in the same way. Letting $\log X=\hat{S}\hat{D}\hat{S}^{-1}$ for $\hat{D}$ diagonal,
$$X^a = \exp(a\log X) = \hat{S} \left(\sum_{n=0}^\infty \frac{a^n \hat{D}^n}{n!}\right) \hat{S}^{-1}$$
which again is fast to compute.
Thinking off the top of my head now, it seems that since all rotations are in a plane, the eigenvalues of a rotation X in $\mathbb{R}^n$ must be $e^{\pm \mathrm{i}\theta}$ for some $\theta$ (once each) and $1$ ($n - 2$ times). Therefore the matrix $I-X$ has eigenvalues $1-e^{\pm\mathrm{i}\theta}$ and $0$ ($n - 2$ times), so its diagonalisation D has a particularly simple form.
Matrix rows or columns are traditionally listed under $(x,y,z)$ order.
Cyclically change the pairs under consideration i.e $(x,y)\to(y,z)\to(z,x)$. The pairs $(x,y)$ and $(y,z)$ show up in the same order in the matrix but the $(z,x)$ shows up in reverse in the matrix. That is the cause of apparent discrepancy but really there is no discrepancy.
For example write
$x'=x\cos \alpha - y \sin \alpha$
$y'=x\sin \alpha + y \cos \alpha$
now change $(x,y)\to(y,z)\to(z,x)$ and $\alpha\to \beta \to \gamma$ and write the three matrices to see how $(z,x)$ part gets flipped.
Edit:
If you want them to look alike then give up the matrix notation and instead write
$y'=y\cos \beta - z \sin \beta$
$z'=y\sin \beta + z \cos \beta$
And
$z'=z\cos \gamma - x \sin \gamma$
$x'=z\sin \gamma + x \cos \gamma$
In each instance if you try to write $\left[ \matrix{ x' \cr y' \cr z'}\right]$ in terms of $\left[ \matrix{ x \cr y \cr z}\right]$ you will see that the mystery goes away.
Best Answer
Background: It is very convenient to use the following notation:
$\mathtt R_{UV}$ is a rotation matrix which transform points from reference frame $V$ into the reference frame $U$. Thus: $\mathbf x_U = \mathtt R_{UV} \mathbf x_V$. The inverse rotation is $\mathtt R_{VU} = \mathtt R_{UV}^{-1}=\mathtt R_{UV}^\top$.
Lets, call the initial frame $O$. I assume you mean with "rotated from the same initial frame" a change in the observer frame/passive transformation (http://en.wikipedia.org/wiki/Active_and_passive_transformation).
Thus, you have the rotation matrices $\mathtt R_{OA}$ and $\mathtt R_{OB}$ (which describe the motion of the observer from $O$ to $A$/$B$, or in other words maps points from $A$/$B$ to $O$). Now, I assume you are interested in $\mathtt R_{AB} = \mathtt R_{AO}\mathtt R_{OB} = \mathtt R_{OA}^\top\mathtt R_{OB}$.
Finally, convert $\mathtt R_{AB}$ into axis-angle...
(In case you have $\mathtt R_{AO}$ and $\mathtt R_{BO}$ and want to calculate $\mathtt R_{BA}$ , you get $\mathtt R_{BA}=\mathtt R_{BO}\mathtt R_{AO}^\top$.)