Seems paradoxical doesn't it? But many features of relativity devastated common-sense intuition about time and space when it first was published, so this seeming paradox is just one amongst a list of many... and comes as no surprise.
Had Newton read the articel that Einstein wrote back in the 17th century, he would probably have been SHOCKED! and responded with the same disbelief as you... however the math matches up beautifully with observation. He would simply have been forced to accept what seems to shatter common sense notions of the meaning of "space" and "time" (past, present, future, meters, seconds, invarient speed of light, etc.)...
John will see bob as slow motion, and Bob will see John as slow motion. Who goes into the future? John goes into Bob's distant future, and Bob goes into John's distant future. Luckily for them, they remnain distantly separated and have high velocity causing high rate of increasing separation. If both of them used cell phones to inform the other of the "funny buisness" at hand... then the time it would take the phone signal to traverse the distance of the two spatialy separated time travlers would more than compensate for any discrepency or contradictions in informed ages (especialy considering that the signal has to "chase after" receeding observer with "less than c closing speed" in rest frame of signal emitter). Since light travels with speed c for both observers, and yet one observer see light to approach receeding observer with less than c, then simultaneity is relative, and neither can agree on precise moment in time when signal was emitted (a "moment in time" is ambiguous and must specificly reference either John or bob, but not both). Because of this, neither would detect any contradictory statements of the other because finite speed of communication signal would make it seem as if the other had "sent with speed c", while contradiction is compensated by other seeing signal as "catching up with less than c" and concluding upon returned reply of informed age of the other, that it is indeed he that is older. The case is symmetric about both observers, therefore both conclude that it is the other who is in "slow time", and according to relativity... both are correct.
Both relative travelers have equal claim to "time travleing" until you bring them back together again. In this case, nature is forced to choose who is older because the limit of spatial separation has approached zero, thereby disallowing for compensating "cell-phone" signal to have difference in simultaneity for either frame. In this case, past and future are defined as same for both observers, and compensating "dis-simultaneity" is no longer valid. For this, nature simply chosses the guy who didn't undergo acceleration to be older. Since the guy who felt G-forces (when he turns back) must conclude that it was he that was in motion all along, then it is in this case that both can no longer claim to be "time travelers", and it must be one or the other. The resulting asymmetry of motion when acceleration is brought into situation, is the determining factor in who nature chooses as the older person.