Try this. Worked for me after nothing else would:
Press Menu from the home screen, then Settings
Under Wireless & Networks, select Data usage
Tap the menu button in the top right corner
Make sure Restrict background data is not selected and Auto-sync data is selected
Let me know if it...