freitasm: The notifications show up eventually. If you don't see a notification but go to an app listing then it will show to you, otherwise it will slowly be distributed to all users. Has been always like this, even in previous Windows Phone versions.
Interesting, I guess this should be improved/fixed..
First time I turned on my phone (out-of-box), once I signed into my microsoft account, the notification app shows I need to update few apps.
Since I reset my phone, the tile did not show any of the apps need to be updated. I went to store, select one of the Nokia app and it shows [update] rather than install. Once I click update, few others apps that need to be updated came out on the store tile notification.