Problem doesn't seem to be related to any particular phone (I have a Lumia 800 but I've read about a HTC Trophy having the same issue) nor any app.
There is no apparent cause (background tasks are on, they aren't too many, battery saving works only when battery is below 10%), nor is there a solution (rebooting, reinstalling the apps, etc.). I may suppose a hard reset could do the trick, but I'm not willing to go that far (I'd rather wait for the next update and hope for the best).
It doesn't look like the OS update has anything to do with this either (although you never know...), 'cause we've had this update for quite a long time before this started happening (I'm experiencing right now).
If you have homebrew apps installed don't worry, my phone is clean and nothing changes.
Every third-party app is affected; if you have this problem and an app is not affected it's just because it updates its tile via push notification.
Weirdest thing is that one of my apps (I'm a developer) was having this issue too, so I tried to execute my background task while debugging the app...and it worked. The way you test this process (for any non-developer reading) is exactly the same way it works for anyone else, but you have the "privilege" to schedule your background task the way you prefer (basically they give you the possibility to make it run every, let's say, 10 seconds, so you don't have to wait 30 minutes to test your code). So, if I say that the task has to run every 10 seconds, it works; if I don't use this privilege and just wait for it to run when the OS says (that is, every thirty minutes), it just never runs (my app is literally never called).
This to say two things:
1) don't bother talk to developers, they can't do anything about it (the fact that every app has this problem is proof enough)
2) it may very well be true what someone else wrote in this forum, that is the standard scheduling may be broken but when you try alternatives (like an app wrote by a manufacturer, which has some privileged access to other APIs) these may work.
My conclusion is: this is an OS problem (evidently triggered by something very uncommon, considering so few people talking about it) and it specifically involves background tasks and nothing else.
F.