同じような問題で困っていましたので投稿させていただきます
私のOSはWindows8.1です。
<PC設定>→<アカウント>→<Microsoft アカウントに関連付ける>→<まず、現在のパスワードを入力してください。>との指示が出ましたので、使っているローカルアカウントのパスワードを入力しました。
次に「お待ちください」と表示され、問題の「Microsoft サービスに接続できませんでした。問題が引き続き発生する場合は、スタート画面で「ネットワークの問題」を検索してください。」の表示がありました。
これではストアアプリの作業などもできませんでしたので、ストアアプリでは、サインイン画面下に出る、「アプリ1つずつにサインインする(お勧めしません)」を選択。この方法だと特に問題なく、サインインすることができました。
つまりPC設定からのサインインだけが不可能ということなのです、何か情報をくださいませ。
**モデレーター注**
統合されたコメントです。
統合前スレッドタイトル : Microsoftアカウントに切り替わらない