SQL Server Rollback nested Stored procedures and linked servers I have read THIS StackOverflow article, and found it enlightening. However, I am having trouble assimilating that knowledge with my limited knowledge of transactions and linked servers. I am trying to do something very similar to the question in that article (Rollback everything from the parent stored proc, as well as what occurred in the sub-proc, if the sub-proc fails), except that my sub-proc does simple inserts into another SQL Server via a linked server.

Do any of the nuances of transactions and rollbacks change in this instance? 

As a side note, we are using AWS EC2 with SQL Server 2008 R2, and we had problems configuring MSDTC a couple months ago. We tried using BEGIN DISTRIBUTED TRANSACTION and such, and could not get MSDTC to play nice despite being able to do simple inserts into the linked server easily without the distributed transaction. Must I use Distributed Transactions, or is the another way around it?
Yes you must use a distributed transaction for this since what you described is a distributed query (transaction across servers). You may want to post a new question regarding your MSDTC issue in EC2.