I wonder why the other games worked.

I think the ISP left the old DNS server up, but wasn't updating it. So it was missing some entries relevant to Destiny, but Elder Scrolls and Halo worked.

I dunno.

Poking around the router I noticed the primary DNS was not the usual one. And although the Xbox was supposed to be getting its DNS automatically from the router, for whatever reason, that wasn't working.

I put in the new primary DNS number manually, got a Destiny update right away, and now I can login. Does Destiny give explicit version mismatch errors? I'm wondering if maybe the IP for the update server was not resolving, and my Destiny client could not connect because it did not have the latest update (it was a small one, about 2 Mb.)

Thanks to everyone for their suggestions!

The only other thing I can think is that the XB1 is able to utilize IPv6, but the 360 is locked to IPv4. If your ISP made (?bad) IPv6 routing changes, that might cause some issues. You could try disabling IPv6 altogether to force an IPv4 connection, maybe?

No option in my router for IPv6 configuration. Pretty sure my ISP is not using it; no other devices on my network are getting IPv6 addresses from it.

UPDATE: Yeah, just checked, IPv6 in the router is already off.

so you have 2 360's and an xbox one? Are the ports all forwarded correctly in your router? Could you move the XBONE to the DMZ?

Xbone is DMZ. I have the 360s and the One but they are not connected at the same time.

I'ved tried with and without DMZ, with explicit port forwarding and with none. It changes the reporting from "strict NAT" to "Open NAT" when I use the DMZ, but the banjo error occurs regardless.

Destiny has been working with the same configuration since launch; I've never had more than the occasional error. Something upstream of me has changed, and now all I get are banjo errors.

My Xbone is DMZed and has Open NAT. The built-in network test and multiplayer test both show no issues.

Sadly, it may be your only hope.

Well, still no luck.

I've uninstalled and reinstalled the entire game (35+ GB), I've changed my MAC address, and I've deleted and recovered my Xbox Live profile.

Still nothing but banjo errors. Looks like my time with Destiny is over. It's been fun.

~m

On my nephews Xbox, it screwed with me like this. I deleted my profile and added it again. Solved problem.

Just deleted and reinstalled.... still banjo errors.

Although it happens on my wife's profile on the same box, but not either of our profiles on either of two 360s, so I don't know. It's also not affecting other games, online or offline. Just Destiny.