If I send two rockets from the Earth in opposite directions, at, say, 60% of the speed of light relative to the Earth, then relative to each other they are travelling at 120% of the speed of light. What is my problem in reasoning?
Is it to do with the fact that due to SR their relative velocities are not 120%, in either of their reference frames? If this is the case, what is the maximum relative velocity that two bodies can have from any reference frame?
Its been a while since I studied relativity, so I wont attempt the math, but I remember covering a similar situation at university. From what I remember, the issue is the reference frame you are considering it from.
When you say they are moving in opposite directions, that is from a specific reference frame, the earth. In that frame, the separation between the two may be increasing at greater than the speed of light, but neither of the individual objects is moving faster than the speed of light relative to you, the observer on earth, therefore not violating any laws of relativity.
From the perspective of one of the rockets, this would be different, the other rocket would in fact be moving away from you at the 0.88c as calculated in or1426's answer.
You've assumed the law to add velocities is the same in special relativity as it is in Gallilean kinematics. This is wrong (as the paradox you've reached shows). Its possible to derive a way to "add" velocities which is compatible with relativity.
Your version is:
\begin{equation} s=v_1 - v_2 \end{equation}
The correct version is:
\begin{equation} s= \frac{v_1 - v_2}{1- \frac{v_1v_2}{c^2}} \end{equation}
With your velocities ($v_1=0.6c$, $v_2=-0.6c$) we get:
\begin{align} s &= \frac{1.2c}{1+ 0.6^2}\\ &\approx0.88c \end{align}
This is how things actually work and is significantly different to the version you used when the velocities are large enough. In particular if you use it you'll always find that two observers will see each other move at less than the speed of light if any third observer sees them both moving less than the speed of light.
On the other hand when the velocities in question are small then this version is very similar to the Gallilean one which is why our instinct works for everyday speeds. For example with $v_1=-v_2 = 0.01c$:
\begin{align} s&= \frac{(0.01+0.01)c}{1+0.01^2}\\ &\approx 0.019998c \end{align}
Very close to the Gallilean answer of $0.02c$.
Edit: I should point out that these formulae are only correct for motion in the same line. More general motion has a more general (and messier) formulae.
