This is a great, but really big question! I'll attempt an answer here, but with the understanding that the acceptance and rejection of Nestorianism goes along lines both theological and political.

Firstly, some background for those unfamiliar. Nestorios was installed as Patriarch of Constantinople in 428 by the Emperor Theodosius II. He had previously lived as a monk and was a student of Theodore of Mopsuestia, one of the most famous Antiochene theologians.

Nestorios entered into a controversy that was already live by the time he got to Constantinople (Grillmeier, Christ in the Christian Tradition, Vol. 1, 451). The controversy was over whether it was appropriate to call Mary the θεοτόκος (Theotokos, 'God-bearer' or, less literally, 'Mother of God') or the χριστοτόκος (Christotokos or 'Christ-bearer'). This may seem like a distinction without a difference, but it was one that had major theological implications. For one, if Jesus Christ is fully God (as the Nicene Creed of 325 affirmed) and is a single person, then we must affirm that Mary is the Theotokos, or else we sacrifice either His divinity or unity of person. Nestorios isn't so interested in defending this - though he claims he affirms both Christ's divinity and that He is not two persons - but is rather more interested, like the Antiochenes in general, in defending the Middle Platonist conception of the impassibility of God (cf. O'Keefe, "Impassible Suffering? Divine Passion and Fifth-Century Christology," Theological Studies, 58 (1997): 39-60). But Nestorios here makes a mistake, I think, in that he forgets that the ultimate subject in a rational being is the person, not the nature. So when he wants to protect the impassibility of the Logos in His divinity (a perfectly orthodox statement to which all parties involved in the Nestorian controversy would agree), He makes the divinity - the nature - the ultimate subject of attribution and thus constrains his own ability to speak about Christ as a single person who is both fully God and fully man.

Now, Nestorios later says later in the Book of Heraclides, which he wrote after his exile in 431, that he never had any issue with the term Theotokos, but we know this is untrue as we have a sermon of his dating from 429-430 where he explicitly takes issue with the word (cf. Loofs, Nestoriana, Sermon 9).

I think what appealed to the East and not the West with respect to Nestorianism is the sort of soteriology put forward by Nestorios. Donald Fairbairn in his Grace and Christology in the Early Church splits Christologies up into two camps: those who see Christ as the one who comes and saves us from the muck and mire of our sins and thus stresses the presence of God with us in the person of Jesus Christ; and a Christology that sees salvation as a work of human effort in which God assists and cooperates (p. 12). The more pessimistic theological anthropology is characteristic of Western soteriology. One only needs to do a cursory read of St. Augustine's writings to see a representative example. But the East tended to have a more positive theological anthropology. Man was not thought of as so damaged and thus was more capable of virtue, even salvific virtue (for an example, look to Gregory of Nyssa's De Hominis Opificio).

What's all this got to do with Nestorianism? Nestorios' Christ, according to his critics (like John Cassian), at least, is one who merits his identity. The Logos knows beforehand how virtuous the human Christ will be and thus cooperates with him in order to achieve salvation (which, again according to Nestorios' critics, is primarily by way of example - and thus verges into Pelagianism)(cf. Nestorios' teacher, Theodore of Mopsuestia, De Incarnatione 7 for this teaching explicitly - cited in Fairbairn 181). The West had already rejected Pelagianism, in large part due to its theological anthropology, and so a Christology which lent itself to a Pelagian soteriology was already suspect. Rather, Cyril of Alexandria (Nestorios' most prominent Eastern opponent - for a good overview, cf. John McGuckin, St. Cyril of Alexandria and the Christological Controversy - and the Western Fathers (Leo, Cassian, etc) stressed the fullness of God's presence in the person of Christ and the impact the Incarnation had on human nature without any prior merit or virtue. If Nestorios could not say that Mary gave birth to the mother of God, could he say that God became man (as Athanasius) or that God died on the cross? If not, then his soteriology would be radically different from that espoused by both Eastern and Western fathers up to that point.

Someone else ought to field the political side of this question, but I know the Church of the East (often dubbed 'Nestorian' erroneously, as they are considerably more Theodorean than Nestorian) thrived in the Persian Empire if only for the fact that they were anti-Roman.

To clarify some of the political dynamics that /u/GregoireDeNarek didn't (in an otherwise excellent answer).

Firstly, all theological debates in the 4th and 5th century interacted with both political activity within the church (theology was never apolitical), as well as access to and support from the Emperor and his court.

For the Nestorian controversy, this polarised in the first half of the period with the political rivalry between Antioch (with whose theology Nestorius was associated) and Alexandria (where Cyril was a dominating influence).

It's worth nothing two things about Cyril. (1) He wasn't a very nice guy. Cyril was, in my view (and not mine alone), a belligerent bully. He utilised Egyptian monks as a form of organised mob violence, and was a repeated source of problems. (2) Cyril's theology comes very close to the opposite problem of Nestorius'. Indeed, the language Cyril used strongly suggested the combination of the divine and human natures into a new single nature, a tertium quid, which view later came to be termed Monophysitism and was itself the cause of significant fracturing in the churches of the Eastern half of the empire, and led to both ongoing controversies and schismatic churches.

As for the 'Nestorian Church'. It's widely acknowledged that this is a misnomer. To understand the political dimensions of what happened to 'Nestorianism' as a movement after its rejection, we need to keep in mind a few other facts: (1) the 'Church of the East' existed as a fairly autonomous entity outside the (Roman) Empire, and given the extent of the Sassanid empire, and this Church's geographical and numerical success, they were perhaps rivals in number to the church within the Roman Empire. (2) The eastern 'border' of the Roman empire shifted, and those border territories were a mixing point between Greek-speaking Christianity, and Syriac Christianity. Syiac was the dominant language of the Church of the East. (3) theological controversies in the Greek-speaking churches (in the 4th and 5th century) turned heavily upon technical theological discussions reliant upon Greek philosophy and Greek terminology. Terminological distinctions that were vitally and fiercely contested in Greek, were often difficult to translate and explain in Syriac (and Latin, for that matter).

So, the ultimate rejection of Nestorianism displaced communities and believers who were adherent to this theology. And they tended to be on the eastern edges of the empire anyway. So they went further east and found a ready acceptance in the Church of the East.

The Church of the East's own history is complicated by the fact that the Persians, in their various incarnations, were locked in a dualistic political struggle against the Roman empire that ebbed and flowed. The ascendancy of Christianity within the R. Empire caused Christians within the Sassanid territory to face greater opposition.

The perception and labelling of the CotE as 'Nestorian' is misguided because it presumes that the influx of Nestorian christians theologically determined the CotE. But, it's more accurate to understand that the CotE existed as an independent church with a long history of its own, which although it subscribed to Nicaea, didn't feel compelled to accept Ephesus in 451, and welcomed Nestorian believers as compatible with their own tradition.

5th century stuff isn't my forte (4th cent. is), but I have a educated interest in CotE stuff and de-stabilising the very Greco-Roman centric version of church history that is the prevalent narrative.