Cuando asignas un Command a un MenuItem dentro de un ContextMenu el metodo de CanExecute que activa el MenuItem no se llama, por un Bug con el Focus().

Esto se soluciona asignandole el Target del MenuItem al ContextMenu.

<pre class="brush: csharp; gutter: true">
  <UserControl.CommandBindings>
    <CommandBinding Command="ApplicationCommands.Save" 
                    CanExecute="CommandBinding_CanExecute" 
                    Executed="CommandBinding_Executed" />
  </UserControl.CommandBindings>
  <UserControl.ContextMenu>
    <ContextMenu>
      <MenuItem Header="Change Background" Command="ApplicationCommands.Save"
      CommandTarget="{Binding Path=PlacementTarget,RelativeSource={RelativeSource AncestorType={x:Type ContextMenu}}}" />
    </ContextMenu>
  </UserControl.ContextMenu>
</pre>