Are you both on the same router? E.g., are you both connected to the same internet modem? There seems to be an issue with Uplay, where only one player can be connected even when working with different Uplay accounts. I don't know if there is a fix for it yet, I only know that the issue isn't unique.
Have you tried contacting Ubisoft's support center? You can find the link under support on their website.
Having the same problem as you, only did not have it about two weeks ago, I found out that another person said it has only happened recently. It appears to be asking for port forwarding, we both port forwarded the number given, still not connecting. I believe it is a recent problem as It was working last month.
Sorry to not be helpful, I imagine its only a temporary bug though...