I've had a lot of trouble recently with connecting my PC to my SharePoint Online tenants via PowerShell. The process is fairly simple and this article is the best starting point: http://technet.microsoft.com/en-us/library/fp161388(v=office.15).aspx.
Having done all the right things, I was running into the following error upon every time I'd run the Connect-SPOService cmdlet: "The Application ID (AppID) for which the service ticket is requested does not exist on the system."
I don't know what that means or where to begin with it, so I hit the web and found nothing useful. Ugh.
Well, today I got lucky. I'm presenting at tonight's meeting of the Phoenix Office 365 User Group and have been spending a few precious lunchtime minutes prepping for tonight. In particular, the facility we meet in does not provide wired network access and so I want to make sure that my virtual machines work are going to play nicely with my wireless NIC today. I disabled my Ethernet NIC and am only on wireless now as I write this.
Somehow, that fixed the issue. I'm guessing it has something to do with my host (Windows 8.1) running Hyper-V and having several different virtual switches that share my wired Ethernet NIC.
I'm now essentially not using any unusual network settings and I've been able to connect to multiple tenants now without a problem. Yay!
I just called and talked to tech support at my ISP and the "The Application ID (AppID) for which the service ticket is requested does not exist on the system" message is occurring because I'm on a residential network instead of a business network. Looks like I'll have to go to the office for these kinds of things. Argh!
I've found success in connecting to my company's VPN for the last year. While that's worked, it's been pain in the neck to connect to VPN on and off all day. Today Max Melcher posted a similar article here: https://melcher.it/2016/02/for-security-reasons-dtd-is-prohibited-in-this-xml-document. Check it out. You might find success in some DNS updates and disabling IPv6.