I tried your method and I am able to add and remove layers to the legend, so long as they are already included in the xaml side. I am not having the same problem using the same method you display.I did this using ESRI's legend sample and your code:
private void remAddLayers()
{
string[] aerialList = {"Points of Interest", "United States"};
esriLegend.LayerIDs = aerialList;
esriLegend.Refresh();
}
Xaml:
<esri:Map x:Name="MyMap" Extent="-15000000,2000000,-7000000,8000000" MouseLeftButtonDown="MyMap_MouseLeftButtonDown">
<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:FeatureLayer ID="Points of Interest"
Url="http://sampleserver3.arcgisonline.com/ArcGIS/rest/services/Fire/Sheep/MapServer/0" />
</esri:Map>
<esri:Legend x:Name="esriLegend" Map="{Binding ElementName=MyMap}"
LayerIDs="Points of Interest"
LayerItemsMode="Tree"
ShowOnlyVisibleLayers="False">
And I was able to add the United States layer.