Had trouble with the native Mail app on Windows 8.1 recently. It would not connect to my Outlook.com email address. Rebooting, toggling the sync options, attempting to update Windows and apps and even a system refresh (due to failed Windows Update installs) did not resolve the problem.
Finally the solution was to remove the Mail app by right-clicking the Mail tile and selecting uninstall. This also removed Calendar and People. Rebooted and then reinstalled. Mail is now syncing as expected!
