Guys registered onto this site to try to help as I promised myself I would if I got it fixed for myself!
I just fixed it after literally trying everything! Even had this issue on 2 separate PCs, which led me down the path that my profile (Microsoft account) was the problem with it replicating across PCs via Sync Settings being enabled.*
Anyway turned out to be relatively simple to fix. Simply uninstall the 4 tied apps (Mail, Contacts, Calendar and People) and reinstall. After reinstall, looked like a slightly updated version was put on via the Windows Store. Straight away I could see all connected services where displayed and after a 3 min sync was completed, everything seems to be working fine.
To uninstall these apps, right click on any one of them and on the bottom app bar choose uninstall. It will prompt to uninstall the 4 at the same time.
As I say this worked for me, so I'm happy. Hope this helps someone else!