I’ve played with various combinations and have determined a consistent work around for the Matchmaking issues present at launch (BL1-GOTY). I have NOT found a way to get the native Matchmaking service to work.
For now I am able to join games, and have others join my games, so long as the game is joined via the Xbox Menus (under Friends/Groups). This only seems to work from a fresh instance of BL1, meaning that every time I quit a game to menu and tried to join a new game it hangs at the “looking for saves” prompt. I had mixed success trying to connect with BL1 not already running.
So, it is possible to play with others for now - just not random games. Please, feel free to add me on Xbox, Steam, whatever (Rune306, thewigglesworth) and I’ll happily join your games or host. Let’s be honest, Borderlands is much more fun with friends! (I’ll be running a marathon campaign leading up to BL3 - hit me up for info.)