I have found a way to work around the problem:
I create an invisible TextBox, bound to the ComboBox, and I bind the command on the TextChanged event of the TextBox.
It's not pretty, but it works...
<ComboBox Name="CbRubrique" IsEditable="True">
<i:Interaction.Triggers>
<i:EventTrigger EventName="SelectionChanged">
<cmd:EventToCommand Command="{Binding CritereChangedCommand, Mode=OneWay}" />
</i:EventTrigger>
</i:Interaction.Triggers>
</ComboBox>
<TextBox Text="{Binding ElementName=CbRubrique, Path=Text, UpdateSourceTrigger=PropertyChanged}" Visibility="Collapsed">
<i:Interaction.Triggers>
<i:EventTrigger EventName="TextChanged">
<cmd:EventToCommand Command="{Binding CritereChangedCommand, Mode=OneWay}" />
</i:EventTrigger>
</i:Interaction.Triggers>
</TextBox>