IntuitioN said:
How does this work? It seems impossible that both clocks can run slower.
To begin understanding how each observer
measures the other's clock clock as running slow, and why this entails neither physical impossibility nor contradiction, you need to see how several special relativistic effects interwork:
(1) moving clocks are measured to run slow
(2) moving metersticks (or anything with length) are measured to be shorter (along the direction of motion)
(3) moving clocks that are synchronized in their own frame are measured to be out of synch
Each of these effects are completely symmetric. Observer A will say that Observer B's clocks run slow (as measured by A) and Observer B will say the same about A's clocks. Same for the other two effects. Effect #3, clock desynchronization, is the most subtle.
It is only by combining all three of these effects that things will make sense. I recommend consulting any of the many elementary books on special relativity available for a detailed explanation.
Another place to start is with a website that explains time dilation using the infamous "light clock":
http://landau1.phys.virginia.edu/classes/109/lectures/srelwhat.html
That links to a short lecture that covers time dilation; the followup lecture explains clock synchronization and simultaneity; the third explains how it all fits together. Be sure to look at all three!
PS: I don't think IntuitioN had the twin paradox in mind when he asked his question. (That will just add confusion, at this point.)