In Before Crisis the 'original' pre-Barret Avalanche is based out of Wutai, and the Turks actually infiltrate the base, plant bombs there, and blow it up. So the connection has been established in the world before, but it's now being added to this new version of FF7's lore.
The whole Wutai story is interesting, as the original game doesn't really go into detail on it. All we know really is that Shinra wanted to build a reactor there, Wutai said no, and then the two went to war. Despite only being mentioned in passing the war is an important backdrop, because the war is where Aerith's mother's husband dies (so when she's waiting at the train station for him to return and discovers Aerith instead, it's from the Wutai war), it's key to pretty much everything about who Yuffie is, and it's also (in CC) one of Zack's greatest triumphs - he's basically the one to end the war.
The Wutai as shown in FF7 is a weird one, because though the game justifies it by saying that post-war, capitulated, the country is reduced to a tourist trap, it doesn't look like a country capable of going to war with Shinra, leave alone a war that'd force Shinra to conscript civilians like Elmyra's husband... even if it is producing ace ninjas like Yuffie. Between this and the line from the president in the trailer about "Wicked Wutai, our sworn enemy", it may be that in this version of the story the war isn't exactly over. If this is true it completely shifts Yuffie's story and motivation, however, as the whole reason she's out in the world stealing and stuff in the original game is because she left Wutai disgusted by her father's surrender to Shinra. So... hmm.