I just got done updating my Lumia 920 (AT&T) and also went in to the Twitter settings and toggled the individual tweet setting off, exited, then went back in and turned it back on, exited again and within 10 minutes I got twitter notifications and they have been working since. Maybe the new update corrected some specific bug that the Twitter app was affected by on some devices... Not sure.