本当に一瞬のちらつきだな
やっぱ　PhoneApplicationPageのshell:SystemTray.IsVisible="True"のときだけの現象みたいだから
Falseにするか、Trueで使いたいなら>>530が言ってるようにinvokeしたら？
this.Dispatcher.BeginInvoke(() =>
{
NavigationService.Navigate(new Uri("/MainPage.xaml", UriKind.Relative));
});