Google Apps Sync Error

[Cmustang87]

When opening Outlook on this computer I'm getting the error: "Cannot open your default e-mail folders. The information store could not be opened"

This happens with another profile as well

This is what I have tried:
1. Start -> All Programs -> Google Apps Sync 2.0 -> Delete saved Google Apps Sync passwords for this profile.
2. Ran scanpst.exe on the PST file it's using.
3. Deleted the profile in Control Panel and recreated with new password (This recreates a PST as well)
4. Uninstalled Google Apps after deleting the profile again, repair install of Outlook 2007. Rebooted.
5. Ensured I was local administrator
6. Logged on as a different user profile, still have the same problem.
7. Created a new PST in C:\test.pst, this allowed me to open Outlook but the folders and everything won't sync properly.
8. Checked that Outlook.exe wasn't launching in compatibility mode.

Any other ideas I should try, I'm almost out of them. I'm able to log into the account via www.gmail.com

EDIT: Just did a full uninstall and reinstall of Outlook 2007, still having the same problem.