One person with this problem couldn't join if the game was running, but if they exited and waited for a Steam invitation, they could accept and the game would load and join from there.
Did you try having your friend host the game and you join?
There should be a fair sized update next week, but I don't know if any connection issues will be addressed (would think so).