I don't think it creates a paradox. It might be mighty irritating to deal with, but so are time zones and train timetables.
Imagine we set up a colony on a world 10 LY (light-years) away from Earth. When we look at them in a telescope, we see what is happening 10 years ago. We receive a message from their government one day in Year 0 that reads:
"Viva la Revolucion! Bite us"
And all other communication ceases.
We send out a fleet of lightspeed spaceships to attack them.
Ten years later, at Year 10, the lightspeed ships arrive to find that the colony had its only engineer get a hair up his ass, sent the message, and destroyed the colony's communication capability. Oh well, no war of independence after all. The lightspeed spaceships send a message to Earth asking for orders. Ten years later the message hits Earth at Year 20, and Earth replies telling them to come home. The reply reaches the colony at Year 30. The ships pack up and head home and arrive back on Earth at Year 40. The crew experiences time constriction such that it seems like little time has passed at all.
Of course this is irritating. We are, after all, just experiencing the same problems on a larger scale that the European colonists suffered in reaching the New World. Communication is slow, and often battles happen in the colony after a peace is struck back home. If I recall correctly, the American Battle of New Orleans was fought after the war ended officially in Europe.
What's the problem of faster-than-light travel? I can imagine us sending a probe to Alpha Centauri that will take 100 years to reach it, then 4.6 or whatever years for the message beamed back to reach us. But if in 20 years we develop an engine that can go twice as fast as the first probe, and we launch it, the second probe would reach the target in Year 70 and beam the data back before the first probe even reached it.
I imagine the technology of speed is a curve such that waiting 100 years expecting to be able to then launch a craft that can make the trip in 1 year is a poor plan. But waiting 10 years hoping to make a craft that can shave more than 10 years off the trip is reasonable.
Faster than light travel would simply result in the traveler leaving behind all that he knows and loves in pursuit of personal gain and adventure, or service to a cause or organization. Because while he may be able to experience 400 years of space trips during his lifetime by using cryogenics or whatever for the bulk of the trip, to the rest of the people on the different colonies thousands of years have passed.
So there isn't really a dilemma. Other than leaving your twin behind of course.