Restrict Background Data should be off, so it sounds like it was off to begin with.
There can sometimes be some lag between the time updates become available and when I get a notification for the update on my phone, so it's possible there can also be some lag with auto-updates. How long have you waited to see if it starts updating on its own?