Exception appeared after Windows 8.1 update

I have a Windows Store app that was running fine for the last 6 months with no exceptions and a 50 minutes average app usage for day (dashboard statistics). Bad ratings will ruin my 4.5 average rating and I need to solve this fast so I will give a bounty to whom helps me solve it. (I have to wait 2 days to be eligible but I will do it)

Today I installed Windows 8.1 update and now my app crashes everytime. This is what is happening:

I have a MediaElement control in my main page and the user can change its source. It has an MediaFailed event callback attached.

Problem 1

Till now MediaElement played fine every source user would choose but now it always fails and MediaFailed event is triggered.

MediaElement ExceptionRoutedEventArgs.ErrorMessage is "MF_MEDIA_ENGINE_ERR_DECODE : HRESULT - 0xC00D36B4"

Problem 2

This is MediaFailed callback that is causing the exception:

private async void MediaElement_MediaFailed(object sender, ExceptionRoutedEventArgs e)
{
    MessageDialog notAvailableDialog = new MessageDialog("Not available", "Ooops");
    notAvailableDialog.Commands.Add(new UICommand("Ok"));
    await notAvailableDialog.ShowAsync();
}

If I catch the exception app shows the dialog and it does not crash. This is the exception:

Message: [System.InvalidOperationException] = {"A method was called at an unexpected time. (Exception from HRESULT: 0x8000000E)"}

Stacktrace: at Windows.UI.Popups.MessageDialog.ShowAsync() at MainPage.d__30.MoveNext() in MainPage.xaml.cs:line 296

UPDATE 1

Problem 2 solved. MediaFailed event is fired twice and because of that 2 MessageDialog were showed at the same time causing the exception. I solved it by not showing more MessageDialog till there is none open.

Problem 1 is not solved. It is making my app useless. My MediaElement is throwing the following error: MF_MEDIA_ENGINE_ERR_DECODE. It means: An error occurred while decoding the media resource.

Another strange behavior is: when deploying app to Simulator it works fine but when deploying to Local Machine decoding fails.

What may be causing that? Before installing Windows 8.1 update decode was working fine.

UPDATE 2

Problem 1 was solved after restarting the computer. Some wasted hours because a CODEC conflict after installing the update.