Ok so I have a domain that I want to sync to Office365 but when I start the Windows Azure Active Directory Sync tool Configuration Wizard I get an error with the following details:

System.Management.ManagementException: Generic failure 
   at System.Management.ManagementException.ThrowWithExtendedInfo(ManagementStatus errorCode)
   at System.Management.ManagementObjectCollection.ManagementObjectEnumerator.MoveNext()
   at Microsoft.Online.DirSync.Common.MiisAction.GetTargetMA()
   at Microsoft.Online.DirSync.Common.MiisAction.IsSyncInProgress()
   at Microsoft.Online.DirSync.Common.PrerequisiteChecks.ThrowIfSyncInProgress()
   at Microsoft.Online.DirSync.UI.IntroductionWizardPage.PrerequisiteValidation()
   at Microsoft.Online.DirSync.UI.IntroductionWizardPage.OnLoad(EventArgs e)
   at System.Windows.Forms.Control.CreateControl(Boolean fIgnoreVisible)
   at System.Windows.Forms.Control.CreateControl(Boolean fIgnoreVisible)
   at System.Windows.Forms.Control.CreateControl(Boolean fIgnoreVisible)
   at System.Windows.Forms.Control.CreateControl(Boolean fIgnoreVisible)
   at System.Windows.Forms.Control.CreateControl()
   at System.Windows.Forms.Control.WmShowWindow(Message& m)
   at System.Windows.Forms.Control.WndProc(Message& m)
   at System.Windows.Forms.Control.ControlNativeWindow.WndProc(Message& m)
   at System.Windows.Forms.NativeWindow.Callback(IntPtr hWnd, Int32 msg, IntPtr wparam, IntPtr lparam)

I have searched far and wide to no avail, this happens before I can even enter any details.

A few notes:

1. The server is not the domain controller
2. Sharepoint 2013 is installed on this server
3. The account I log in with and run the application with is a domain and enterprise admin
4. I right click and run as administrator when I start the application

So when I click continue on the error and go through the steps I get two possible scenarios that change from time to time at now predictable rate:

1) I just get an error, generic failure.

2) I get an error "Cannot start service MSOnlineSyncScheduler on computer '.'."

Any help?