Hey all,
Found a fix that worked for me. Apparently the background data restriction option doesn't necessarily remove an app-specific restriction of the same kind. So then you have to remove that restriction for the exchange services. I went through all those forums for the past week and I ended up trying something that worked for me, it's finally working. Try the following (the names of the options and menus might vary for you, I'm on the Nexus 4).Steps below
Go to settings
Go to Data Usage
After you get there, a list of apps and the amount of data they consume will show up below.
Scroll down till you find the one titled; Exchange Services
Open it, Scroll all the way down (past the View App Settings option). There should be a checkbox to Restrict Background Data. In my case, even though I had removed the background data restriction option from the general menu, it was still checked here.
Make sure that this box is unchecked, and voila. Hope it works.
Good luck