Can't login to xbox live : error 8007065B

If suddenly you are unable to login to xbox live even if you where able before (on an xbox 360 in my case). If the "network test" says that you have access to internet and xbox live servers, continue reading !

Everywhere on the internet they talk about your profile that may be corrupt, because you changed your gamertag on whatever. I tried to delete it and re-download it but ended up with an error 80070428 when doing so.

Finally, the source of the problem was that even if the network test said that I was able to reach xbox live servers, it also warned me that my NAT configuration may reduce multiplayer games quality by preventing me from earing the voice of other players and bla bla bla... I omitted this warning, because it does not seamed important. BUT IT IS. Apparently, you can't connect to Xbox live at all because of this. (on an Xbox 360 at least, because it seems to work fine on Xbox one).

TL;DR

To solve this issue, you must open your router's admin panel and enable UPnP (Universal Plug and Play). (On my router its under a tab called "Advanced network settings"). Then reboot the router if needed, and try again to connect to Xbox live.

It solved all my problems !