The relation of magnetic field and the vector potential is independent of the coordinate system. My first attempt I got the same result, however, soon I realized that the coordinates also have to undergo the same rotation. So if one has the following vector potential
$$ \mathbf{A}(x,y,z) = \left( \begin{array}{c} 0, & Bx, & 0 \end{array}\right)^T $$
so rotating it by the well-known rotation matrix gives:
$$\mathbf{A'}(x,y,z)=\left(\begin{array}{c} Bx \sin\theta, & Bx \cos\theta, & 0 \end{array}\right)^T $$
For the curl computation, the curl has to be computed in the rotated coordinates. The rotated coordinates are:
$$ x' = \cos\theta x + \sin\theta y \quad \text{and} \quad y' = -\sin\theta x + \cos\theta y$$
Actually we need the inverse relation as we want to express the old coordinates by the new ones (fortunately we need it only for x):
$$ x = \cos\theta x' - \sin\theta y' $$
We now express the rotated vector potential by the new coordinates:
$$ A'(x',y',z') = ( \begin{array}{c} B(\sin\theta \cos\theta x' - \sin^2 \theta y'), & B(\cos^2\theta x' - \sin\theta\cos\theta y'), & 0 \end{array} )^T$$
If we take now the curl of $\mathbf{A}$ we get the desired result:
$$ \mathbf{B'}=\nabla' \times A'(x',y',z') = \left( \begin{array}{c} 0, & 0, & B(\cos^2\theta + \sin^2\theta )\end{array} \right)^T$$
So the raised question has nothing to do with gauge invariance, it is all about rotational invariance.