Would possibility of instant communication break physics? I recently read a sci-fi book, where some (very few) people can communicate telepathically, which happens to be instantaneous.
So, every spaceship has a crew member who telepathically communicates with his/her partner on Earth.
Would this lead to a cause/effect paradox? How and why?

More about the book, in case anyone is interested:
Heinlein: Time for the Stars -
The book is narrated by Tom, a young man, who discovered he can telepathically communicate with his twin brother Pat. At age 16, they are hired as special communicators by Long Range Foundation. Tom leaves on a spaceship, while Pat stays on earth, and the pair serves as a communication link between Earth and the spaceship.
The rocket accelerates towards almost light speed. As the speed increases, the twins find it increasingly hard to communicate, because of time dilation.
Back on Earth, Pat gets married, and has a daughter, while Tom is still a teenager...

ADDED:
One thing that makes this different from generic FTL communication is that each pair of communicators started on Earth. Most are twin brothers/sisters, and there is also a set of triplets, where one stays on Earth, and the other two leave with two different spaceships into two different directions.

So the only way to make sense of this is to say that there is some
  distinguished frame of reference whose simultaneity dominates. For
  instance, perhaps some bond forms between Tom and Pat while they are
  both on Earth, and this bond is formed specifically in reference to
  the Earth's frame of reference. When Tom goes off into space, the bond
  retains this frame of reference. It's "set" on Earth's frame of
  reference, regardless of what Tom and Pat do.

There is definitely a special bond between each pair of communicators. They are either twins, or two people who spent a lot of time together to develop telepathic communication.
As the whole project originated on Earth, all these communicator bonds are "set" on Earth's frame of reference (whatever that means...)
 A: In special relativity, there is no objective meaning of "simultaneous". People in different frame of references disagree as to what is "simultaneous". So the only way to make sense of this is to say that there is some distinguished frame of reference whose simultaneity dominates. For instance, perhaps some bond forms between Tom and Pat while they are both on Earth, and this bond is formed specifically in reference to the Earth's frame of reference. When Tom goes off into space, the bond retains this frame of reference. It's "set" on Earth's frame of reference, regardless of what Tom and Pat do.
This wouldn't violate the basic rules of relativity, but it would violate some principles that scientists generally accept. For instance, there's something called the Causality Ordering Principle, that says that if A causes B, then A will be before B in all frames of reference. In the situation you present, however, Tom can communicate something to Pat, and thus Pat knowing something can be caused by Tom communicating that, and yet there will be frames of reference in which Pat knowing it comes before Tom communicating it. And if there is another set of twins that have their bond "set" in that other frame of reference, then you could relay messages between those four people in such a way that someone could get a message from their own future (e.g. old Pat could send a message to his younger self).
One possible interpretation is that the twins are actually communicating with someone in another universe. So if Pat talks to his younger self, he is simply talking to someone in another universe that happens to be exactly like he was in his past.
A: Suppose you had a telepathic phone that could call anywhere in the universe right now. You call your friend in the Andromeda galaxy to say hello. He says, "Hey, stay on the line, I am going to call you back on my other line" (also with instant telepathic connection).
Well, the Andromeda galaxy is moving towards us at 300 km/s (0.001$c$), so when he calls you back from 2 million light years away, he is now talking to the Earth 2000 years in our future.
And now so are you.
In summary: Right now in the Andromeda galaxy, "right now" on Earth is somewhere around 4019 AD.
A: I'm pretty sure that instant communication would give us evidence that relativity is kind of wrong.
Relativity is compatible with all the evidence we have now. Instant communication would give us evidence that we can't get now. Evidence that relativity says will not exist. 
I don't know what new physics we'd get that replaced relativity and incorporated the new evidence. It would be compatible with relativity about everything that relativity now correctly predicts. 
Maybe that's a bad way to say it. Maybe we would simply get new interpretations of relativity, and the interpretations that are incompatible with the reality of simultaneity would be discarded. 
A: 
Would possibility of instant communication break physics?

No. Not at all. 

I recently read a sci-fi book, where some (very few) people can communicate telepathically, which happens to be instantaneous. So, every spaceship has a crew member who telepathically communicates with his/her partner on Earth. Would this lead to a cause/effect paradox? How and why?

No it wouldn't. That's a myth based on misunderstanding. Unfortunately such myths tend to get popularized, and eventually taken as gospel truth by the paying public. The way to appreciate this is to use Einstein's operational definition of time: time is that which a clock measures. A clock is a device that features some regular cyclical "local" motion, that's all. Then it displays an accumulated version of this on the clock face. There is nothing you can do to make this accumulated measure of motion reduce. There is no message you can send, and there is no way you can move to "turn back time". In similar vein there is no message you can send and no way you can move to make cause precede effect. It might affect the way you see things, but it doesn't change those things one iota. 
Moreover, it doesn't matter whether the clock is close to you, or some distance away. Don't be seduced by expressions such as "in my frame of reference", because in the context of special relativity, your frame of reference is little more than your state of motion. And don't be seduced by the Andromeda paradox. Changing your state of motion doesn't affect Andromeda one bit. Remember that this "paradox" came from Roger Penrose, the guy who gave us the parallel antiverse. Take it with a pinch of salt. And don't forget that the CMBR serves as an "absolute" reference frame of sorts. See this question. Everybody can gauge their motion through the universe using the CMBR dipole anisotropy, and everybody can work out that the universe is circa 13.8 billion years old.   
It's like what Steve said in his comment. FTL communication wouldn't break physics, but it would falsify the block universe interpretation of SR. It would also clear up some of the "woo" that tends to gain popularity when it shouldn't. 
