The solution is to set NotifyOnSourceUpdated on your Binding to true and use the SourceUpdated event in your EventTrigger like so:
<ComboBox SelectedValue="{Binding Mode, NotifyOnSourceUpdated=True}" SelectedValuePath="Key" ItemsSource="{Binding MyModes}" DisplayMemberPath="Value" >
<i:Interaction.Triggers>
<i:EventTrigger EventName="SourceUpdated">
<i:InvokeCommandAction Command="{Binding DataContext.SetModeCommand,RelativeSource={RelativeSource AncestorType=UserControl,Mode=FindAncestor}}" CommandParameter="{Binding}" ></i:InvokeCommandAction>
</i:EventTrigger>
</i:Interaction.Triggers>
</ComboBox>