\begin{equation} Xa = \begin{bmatrix} a_1x_{1,1} + a_2x_{1,2}\\ a_1x_{2,1} + a_2x_{2,2}\\ \end{bmatrix} \end{equation} and \begin{equation} X^Tb = \begin{bmatrix} b_1x_{1,1} + b_2x_{2,1}\\ b_1x_{1,2} + b_2x_{1,2}\\ \end{bmatrix} \end{equation} and \begin{equation} Xa+X^Tb = \begin{bmatrix}a_1x_{1,1} + a_2x_{1,2} + b_1x_{1,1} + b_2x_{2,1}\\ a_1x_{2,1} + a_2x_{2,2}+ b_1x_{1,2} + b_2x_{2,2}\\ \end{bmatrix} = \begin{bmatrix}(a_1+b_1)x_{1,1} + a_2x_{1,2} + b_2x_{2,1}\\ (a_2+b_2)x_{2,2} + a_1x_{2,1} + b_1x_{1,2}\\ \end{bmatrix} = \begin{bmatrix}c_1 \\ c_2\\ \end{bmatrix} \end{equation} but $X$ is a rotation matrix gives us that \begin{equation} Xa+X^Tb = \begin{bmatrix}(a_1+b_1)\cos\theta - a_2\sin\theta + b_2\sin \theta \\ (a_2+b_2)\cos\theta + a_1\sin\theta - b_1\sin\theta\\ \end{bmatrix} = \begin{bmatrix}(a_1+b_1)\cos\theta +(b_2- a_2)\sin\theta \\ (a_2+b_2)\cos\theta + (a_1 - b_1)\sin\theta\\ \end{bmatrix} \end{equation} (if you only have $X^TX= I$ then you have to consider the extra case there $\sin \theta \to -\sin \theta $; i.e. rotation composed with reflection. Notice that $X$ is a rotation implies $X^TX= I$!) and therefore that \begin{equation} Xa+X^Tb = \begin{bmatrix}(a_1+b_1)\cos\theta +(b_2- a_2)\sin\theta \\ (a_2+b_2)\cos\theta + (a_1 - b_1)\sin\theta\\ \end{bmatrix} = \begin{bmatrix}c_1 \\ c_2\\ \end{bmatrix} \end{equation} and therefore (by using the triangle inequality) you don't have a solution if for example \begin{equation} \frac{|(a_1+b_1)|}{\sqrt{2}} +\frac{|(b_2- a_2)|}{\sqrt{2}} < |c_1| \end{equation} and like wise for the second condition \begin{equation} \frac{|(a_2+b_2)|}{\sqrt{2}} +\frac{|(a_1- b_1)|}{\sqrt{2}} < |c_2| \end{equation} and you can probably come up with all kinds of other tests for failure, but here is the most general one:
An alternative/equivalent way to look at it is that you have an overdetermined system of 3 equations and 2 unknowns of the form
\begin{equation} \begin{array} & ax & + & by & =& c_1\\ cx & + & dy & =& c_2 \\ x^2 & + & y^2 & =& 1 \\ \end{array} \end{equation}
where $a = a_1+b_1$ , $b=a_2- b_2$, $c = a_2+b_2$, and $d = a_1- b_1$; which is highly unlikely to have solutions.
Therefore you have solutions iff the solution to the system of equations \begin{equation} \begin{array} & ax & + & by & =& c_1 \\ cx & + & dy & =& c_2 \\ \end{array} \end{equation} also satisfies the condition $ x^2 + y^2 = 1 $.
If you want to work out the $n=3$ case you can do the same exact thing but use the Euler angles; it will be long and tedious but you can probably get some kind of condition on the solutions.