Outlook 2007→2010にアップグレードした直後や再セットアップを掛けた直後に、今まで利用していたExchange Onlineのアカウントに対してパスワード入力が求められ、正しい値を入れても受け付けられなくなる様な事象が発生することがあります。
また、新規でセットアップしたOfficeに新規のアカウントを作成しようとした場合も、同じくパスワードの入力が求められ、プロファイルのセットアップが完了できない事があります。
これは、Outlookが新しいOffice365の必須要件を満たしていない場合に発生します。（Windows Updateにより最新の更新プログラムが当たっている場合には発生しません） Office365向けの更新プログラムは、Outlook 2007の場合はKB2583910、Outlook2010の場合はKB2553248として公開されています。
このプログラムをインストールすることにより、新しいOffice365にも接続できるようになります。
テナントのアップグレードを実施される前に、管理者の方はOutlookの更新プログラムが当たっているかどうかを今一度ご確認されることをお勧め致します。