Multiplayer Service Log in Error

Whenever I try playing any sort of multiplayer game I receive this error saying “Multiplayer Service Log In Error” “Unable to log in to multiplayer service. Please try again.”

I could play the game fine a few days ago but I recently reinstalled windows and after re downloading the game I get this error. Teredo is working perfectly fine, I have tested the free Windows Store version of the game and multiplayer works just fine on that.