Дох, нашел ответ.Не добавлено
<Capability Name="ID_CAP_PUSH_NOTIFICATION"/>
в файл WMAppManifest.xml.
Немного вводит в заблуждение, поскольку в документации для ShellTileSchedule говорится, что она обновляет плитку "без push-уведомлений".По крайней мере, теперь это работает:)