The problem is that special relativity predicts that the laws of physics are invariant under every reference frame.
If you modify special relativity, choose a special reference frame, and then say, "instantaneous communication works in this frame and only this frame", then you can make up a consistent theory about the universe where you have faster than light communication*. But this already violates two big parts of physics. Firstly, special relativity postulates that there is no privileged reference frame, so we already have a major contradiction with known laws. Secondly, say the communication takes place through light -- the electromagnetic field. As a quick refresher, part of Maxwell's equations can be written $\varepsilon_0\nabla \cdot {\bf E} =\rho$, where $\rho$ is the charge, $\varepsilon_0$ is a constant, and ${\bf E}$ is the electric field. So let's say that the coupling takes place in $\rho$, and that:
$\varepsilon_0\nabla \cdot {\bf E} =\rho$ everywhere, but that in a certain region, in our privileged reference frame, $$\varepsilon_0\nabla \cdot {\bf E}(\mathrm{Earth},t)=\varepsilon_0\nabla \cdot {\bf E}(\mathrm{Alpha\ Centauri},t)=\rho(\mathrm{Earth},t)+\rho(\mathrm{Alpha\ Centauri},t)$$
But this equation no longer respects Lorentz invariance! That is to say, our modified Maxwell's equations would be different in different reference frames! This is VERY bad, and betrays the entire history of the development of special relativity. So, to summarize:
You would violate the postulates of special relativity by introducing a privileged reference frame. This isn't a nail-in-the-coffin by itself, because -- although the laws of physics are the same -- the rest frame of the cosmic microwave background is a sort-of special frame.
You violate Lorentz symmetry, which has never been observed before. ("No Lorentz violations could be measured thus far, and exceptions in which positive results were reported have been refuted or lack further confirmations.")
However, this is all assuming you stick to a single reference frame. If you allow instantaneous communication to occur in just two distinct reference frames, then you do violate causality**.
No comment on viewing it in the framework of general relativity.
*(The reason I say this: I challenge you to draw a Minkowski diagram, using whatever timelike lines you want but only a set of parallel spacelike lines, in which backwards time travel is physically realized. You can't do it!)
**Draw a Minkowski diagram in 1+1 dimensions that contains a parallelogram with all sides spacelike and all sides representing an instantaneous communication between two points. By changing your frame of reference, any one of these four points could have caused the other three. This Minkowski diagram is plotted below. Lets say Earth operates by the rule that it will send a declaration of war if it doesn't hear from the aliens. It doesn't hear it, so it sends a declaration of war. This causes the aliens to rethink things and quickly send a declaration of peace by instantly (in some frame) sending a message to outpost 1, which instantly (in some frame) sends a message back to the aliens (this is ab event labeled "outpost 2" and is at an earlier time), which instantly (in some frame) sends a message to Earth before they send the declaration of war, causing them not to send the declaration of war in the first place. Contradiction!
In the following images, each blue line represents a "person". They are all sitting still with respect to one another. The vertical axis is time, and the horizontal axis is position. The yellow dots are NOT stars! A star would be a line, because it exists over time. The yellow dots could be explosions or supernova -- they are events in spacetime, not objects sitting in space.
The frame with instantaneous Earth-alien and outpost1-outpost2 communication:
The frame with instantaneous alien-outpost1 and outpost2-Earth communication:
Animation of the transformation under which the laws of physics must be invariant (ie, animation of the lorentz transformation):
This is the Mathematica source used to generate the images:
gamma[v_]:=1/Sqrt[1-v*v];
lorentz[v_]:=Function[{x,t},gamma[v]{x-v t,t-v x}];
starpts=Thread[{RandomReal[{-2,6},100],RandomReal[{-4,4},100]}];
starsizes=RandomReal[{0.001,0.01},100];
Diagram[v_]:=Module[{p1,p2,p3,p4,p5,p6,p7,p8,p9,p10},{p1,p2,p3,p4}=lorentz[v]@@@{{0,0},{2,1},{4,0},{2,-1}};
p5={0,-10};p6={0,10};p7={2,-10};p8={2,10};p9={4,-10};p10={4,10};
{p5,p6,p7,p8,p9,p10}=lorentz[v]@@@{p5,p6,p7,p8,p9,p10};
stars=MapThread[{PointSize[#1],Point[#2]}&,{starsizes,lorentz[v]@@@starpts}];
plot1=Graphics[{Red,
Arrow[{{0.2,0-2},{0.6,0-2}}],Text["space",{0.4,0.2-2}],
Green,Arrow[{{0.2,0.4-2},{0.2,1.0-2}}],Text["time",{0.4,0.6-2}],Blue,Line[{p5,p6}],Line[{p7,p8}],Line[{p9,p10}],
White,Arrow[{p1,p2}],Arrow[{p2,p3}],Arrow[{p3,p4}],Arrow[{p4,p1}],Text["Earth",p1+{0,0.13}],Text["Aliens",p2+{0,0.13}],Text["Outpost 1",p3-{0,0.13}],Text["Outpost 2",p4-{0,0.13}]},Background->Black,PlotRange->All];
plot2=Graphics[{Yellow,stars}];
Show[plot1,plot2,PlotRange->{{-0.5,5.1},{-3,3}}]];
Export["EarthToAliens.png",Diagram[0.5]];
Export["AliensToOutpost.png",Diagram[-0.5]];
Export["change.gif",Join[Table[Diagram[v],{v,-0.5,0.5,1/100}],Table[Diagram[v],{v,0.5,-0.5,-1/100}]],"DisplayDurations"->1/30];
