Yes, you're quite correct that in the example you describe Andromeda can be moving faster than the speed of light. But that's perfectly in accord with special relativity. It's just that the rule that nothing can move faster than the speed of light is true only for unaccelerated motion.
Although beginners are (usually) taught special relativity using Einstein's two postulates this is an approach that doesn't extend easily to accelerated motion, let alone the curved spacetimes we encounter in general relativity. A better way to understand relativity is as the spacetime geometry defined by the Minkowski metric:
$$ c^2d\tau^2 = c^2dt^2 - dx^2 - dy^2 - dz^2 \tag{1} $$
where $c$ is a constant that is equal to the local speed of light. This equation tells you everything about special relativity. For example it's straightforward to use it to derive time dilation and length contraction. The $(t, x, y, z)$ are your coordinates i.e. the time and space coordinates system you've set up using your rulers and clock. If something moves a small distance $dx, dy, dz$ (as measured with your rulers) in a time $dt$ (as measured with your clock), then the equation gives us the corresponding value $d\tau$, which is called the proper time. If you aren't moving (in your coordinates) then $dx = dy = dz = 0$ and equation (1) simplifies to:
$$ c^2d\tau^2 = c^2dt^2 $$
or:
$$ d\tau = dt $$
So this mysterious quantity called the proper time is just the time measured by an observer who is stationary in the coordinate system being used.
We can easily show that equation (1) forbids faster than light travel. Since the proper time is just a time measured by a stationary observer it must be a real number so in equation (1) we must have $c^2d\tau^2 \ge 0$. If $c^2d\tau^2$ was negative when we took the square root we'd get an imaginary number. So let's put this condition into equation (1) to get:
$$ c^2dt^2 - dx^2 - dy^2 - dz^2 \ge 0 $$
For convenience we'll choose our axes so the $x$ axis is along the direction of motion, which means $dy = dz = 0$, and this simplifies our equation to:
$$ c^2dt^2 - dx^2 \ge 0 $$
or with a bit of rearrangement:
$$ \left(\frac{dx}{dt}\right)^2 \le c^2 $$
and since $dx/dt$ is just the velocity $v$ we get:
$$ v^2 \le c^2 $$
and the modulus of the velocity must be equal to or less than the speed of light (I say modulus because when we take the square root of $v^2$ the result can be $\pm v$).
By now you're probably wondering what the point of all this, and how it's relevant to the question, but now I shall reveal all! The Minkowski metric (1) only applies to a non-accelerating observer. Technically you can show this by using the metric to calculate the four-acceleration, and you'll always get the value zero i.e. not accelerating. Anyhow, if you're accelerating with an acceleration $a$ then the metric that applies to you is the Rindler metric not the Minkowski metric. This can be written in many ways, but for our purposes the simplest is:
$$ c^2d\tau^2 = \left(1 + \frac{a}{c^2}x \right)^2 c^2 dt^2 - dx^2 \tag{2} $$
where I've assumed we're accelerating in the $x$ direction so $dy = dz = 0$. Let's play the same trick that we did before, and require that $c^2d\tau^2 \ge 0$, in which case we get:
$$ \left(1 + \frac{a}{c^2}x \right)^2 c^2 dt^2 - dx^2 \ge 0 $$
or rearranging as we did before:
$$ \left(\frac{dx}{dt}\right)^2 \le \left(1 + \frac{a}{c^2}x \right)^2 c^2 $$
This looks comparable to the result we got before except for that factor of $(1 + ax/c^2)^2$, where $x$ is the distance measured in the direction we're accelerating. This factor can be greater than one, and that means the maximum possible velocity can be greater than $c$. In fact we can make the maximum possible velocity arbitrarily large just by going to a big enough value of $x$. This is why in your example Andromeda can be moving towards the travelling twin at a velocity greater than $c$.
But there's a very important principle that applies even to general relativity as well as accelerated motion in special relativity - the local speed of light can never exceed $c$. By local I mean the speed measured at the observer's location. In this case the observer is positioned at $x = 0$, and if we put $x = 0$ into our equation above we find:
$$ v^2 \le c^2 $$
Just as we did before.
A few closing comments: you'll know that distant galaxies are moving away from us, and that if you go far enough away the galaxies will be moving away from us faster than the speed of light. This is generally explained away by saying that it's spacetime expanding rather than the galaxies moving, though that doesn't change the fact that the galaxies really are moving away from us faster than $c$. This is the same sort of thing that's going on with accelerated motion. I see Asher has made the point in one of his comments that what's really going on is space shrinking. Quite true, but the fact remains that in the example you give Andromeda really is moving towards the travelling faster than the speed of light.
