I'm not able to reproduce the issue with the following sample. I use a button click event to toggle the position of GroupLayer and I do see Legend control and map reflect the change in layer order. Did I miss anything?
<Grid x:Name="LayoutRoot" >
<esri:Map x:Name="MyMap" WrapAround="True" Extent="-15000000,2000000,-7000000,8000000">
<esri:ArcGISTiledMapServiceLayer ID="Street Map"
Url="http://services.arcgisonline.com/ArcGIS/rest/services/World_Street_Map/MapServer"/>
<esri:ArcGISDynamicMapServiceLayer ID="United States" Opacity="0.6"
Url="http://sampleserver1.arcgisonline.com/ArcGIS/rest/services/Specialty/ESRI_StateCityHighway_USA/MapServer"/>
<esri:GroupLayer ID="MyGroupLayer">
<esri:FeatureLayer ID="Points of Interest"
Url="http://sampleserver3.arcgisonline.com/ArcGIS/rest/services/Fire/Sheep/MapServer/0" />
</esri:GroupLayer>
</esri:Map>
<Button Content="Test" Click="Button_Click" VerticalAlignment="Top" HorizontalAlignment="Center"/>
<Border Background="#77919191" BorderThickness="1" CornerRadius="5"
HorizontalAlignment="Right" VerticalAlignment="Top"
Margin="20" Padding="5" BorderBrush="Black" >
<esri:Legend Map="{Binding ElementName=MyMap}"
LayerItemsMode="Tree"
ShowOnlyVisibleLayers="False">
<esri:Legend.MapLayerTemplate>
<DataTemplate>
<StackPanel Orientation="Horizontal">
<CheckBox Content="{Binding Label}"
IsChecked="{Binding IsEnabled, Mode=TwoWay}"
IsEnabled="{Binding IsInScaleRange}" >
</CheckBox>
<Slider Maximum="1" Value="{Binding Layer.Opacity, Mode=TwoWay}" Width="50" />
</StackPanel>
</DataTemplate>
</esri:Legend.MapLayerTemplate>
<esri:Legend.LayerTemplate>
<DataTemplate>
<CheckBox Content="{Binding Label}"
IsChecked="{Binding IsEnabled, Mode=TwoWay}"
IsEnabled="{Binding IsInScaleRange}" >
</CheckBox>
</DataTemplate>
</esri:Legend.LayerTemplate>
</esri:Legend>
</Border>
</Grid>
</UserControl>
private void Button_Click(object sender, RoutedEventArgs e)
{
var l = MyMap.Layers["MyGroupLayer"] as GroupLayer;
var index = MyMap.Layers.IndexOf(l);
MyMap.MoveLayer(index, index == 1 ? 2 : 1);
}