A relative time dilation paradox. Let us assume that there are two astronauts A and B who are floating in space. A sees B passing by and vice versa. A sends signals to B every minute. According to A since B is moving his clock will be slower. So B will receive the signals prior to the appointed minute. The same argument can be applied for B who will conclude A's clock is running slow. Who is right?
 A: Both are right. Any moving clock is slower than a clock at rest, from the perspective of the frame at rest. 
Maybe this simplified freehand graphic (apologies for its lack of precision) helps to see that both A and B feel the same about each other's time dilation:

Let's say that the red axis represents A and its proper time measured in minutes (first eight minutes are showed). Green axis and its numbers represents B observer. 
Light or radio signals from A to B, represented in red oblique lines, are fired on a minute basis. Six of them are showed, that took six minutes of A proper time. However, these six signals from A to B take some eight minutes in B proper time. B concludes that A clock is slower. The same holds if we invert the situation (green lines from B to A). Well, almost the same (the last green line is intended to go from green 6 to red 8, blame my trembling fingers). 
A: The key is to remember that you need to pick a reference frame, and stick with it.  So, let's say we are A.
We see B pass by us.  Let's say, that B intends to travel 4 light years, turn around, and then come back.  B accelerates away from us, reaches 80% of the speed of light, and begins his journey. According to us, how long will it take? If $d$ is the distance to his destination, then total time should be $t=\frac{2d}{v} = \frac{8 \,\text{lightyears}}{0.8\,c} = 10$ years.  So, we say that 10 years will pass until B returns to us.
How long do we say B will say the journey will take?  Multiply our time by the Lorentz factor, $$t'=\frac{t}{\sqrt{1-\frac {v^{2}}{c^{2}}}} = 6$$ B will only age 6 years when he returns, compared to the ten years we have aged.
How do B's calculations compare?  Well, due to length contraction, the distance to his destination becomes our distance (4 light years) divided the Lorentz factor (since he sees everything moving by him, he says everything else is becoming length contracted.), which gives 2.4 light years.  Since he is travelling there and back, the total distance traveled is 4.8 light years.  Since his velocity is .8c, the total elapsed time is $t=\frac{d}{v}=\frac{4.8\, \text{lightyears}}{0.8\,c} = 6$ years.  
So, when you include ALL effects (time dilation and length contraction), we can see the numbers work out such that B has measured 6 years, and A has measured 10.
So, what decides who elapses less?  This is key - it's the one who had to accelerate.  Whatever B used to get his journey started forced him to accelerate, so he was a non-inertial observer.  So, he ended up elapsing less time.  Similarly, a rocket leaving earth will elapse less time, since he was the one who had to accelerate away.
Now, you may ask, half way through the journey, what are the numbers?  This is a meaningless question - since nothing can be transferred faster than light, either a signal must be sent (the same conclusion will hold), or they must meet up (as in our example).  So, you can see, when the two observers meet up, they will find the one who accelerated elapsed less time.  That's the whole origin pf the 'paradox' - they both can say the other's clock is slower.  However, when you do the calculation (when they meet up to look at each other's clocks), you will find that B elapsed less.
