Well this is frustrating.

I am in a chat, logged into Xbox live, getting party invites and can play other games, but Destiny claims that I am not connected to the internet.

I did a speed test and am getting 11 mbps down and 4 mbps up. What gives?

If you're using an XBL trial membership on an Xbox 360, you're SOL. That's the only thing I can think of.

I still had a cloned Mac address from the last time I had my box at a hotel, I reset my Mac and it works now.