We need direct witnesses.
Oh by the way, a simple "yes" is not enough of a response to a warning, it must be "yes I am aware of the punishment and prepared to do anyway." (Rambam Sanhedrin 12:3, אפילו אמר יודע אני, פטור: עד שיתיר עצמו למיתה, ויאמר על מנת כן אני עושה)
As for the warning, the Gemara says "even if a demonic voice said don't do that or you'll get punished and the fellow acknowledged it", that would count as the warning. The warning is just to clarify that his act is intentional.
Similarly the Rambam codifies "even if a voice said don't do it", that's considered a warning. (Rambam's code consistently omits the whole demon business, but the idea is the same.) So certainly a telephone warning would count.
Rambam, Laws of Sanhedrin and the Punishments under their Jurisdiction, 12:4:
ובין שהתרה בו אחד מן העדים, או שהתרה בו אחר בפני עדים--אפילו אישה או עבד, אפילו שמע קול המתרה ולא ראהו, ואפילו התרה בעצמו--הרי זה נהרג.
The warning could have come from one of the witnesses, or someone else in the witnesses' presence ... even if he heard a voice warning but did not see him, even if he warned himself!
The only caveat in your phone case is that the witnesses must be aware of the warning, and of the perpetrator's acknowledgement thereof. So it would have to be on speakerphone!