I was able to connect to a strangers game last night. Brother wasn't available but I wanted to see if things had changed. I sent them a message and asked how they set up the game - the response was "pressed start, went to connectivity settings and hit open to all".
I have one guess... I am at work, but if someone is bored, try connecting without being in the same party. Cannot imagine it would help, but on xbox360 Dark souls wouldn't let you play together if you were in the same party.
I am grasping for straws here.
