Is Legend.LayerIDs property set? If yes, this needs to include the new layer ID's. If not, does your new GraphicsLayer have a renderer? You can try the following code:
<Grid x:Name="LayoutRoot">
<esri:Map x:Name="MyMap" WrapAround="True">
<esri:ArcGISTiledMapServiceLayer
Url="http://services.arcgisonline.com/ArcGIS/rest/services/World_Topo_Map/MapServer" />
</esri:Map>
<esri:Legend Map="{Binding ElementName=MyMap}"
LayerItemsMode="Tree"
VerticalAlignment="Top" HorizontalAlignment="Right" />
<Button VerticalAlignment="Top" HorizontalAlignment="Left" Content="Add Layer" Click="Button_Click"/>
</Grid>
private void Button_Click(object sender, RoutedEventArgs e)
{
var l = new GraphicsLayer() { ID = "MyLayer" };
l.Renderer = new SimpleRenderer()
{
Symbol = new SimpleMarkerSymbol()
{
Color = new SolidColorBrush(Colors.Blue),
Size = 20d,
Style = SimpleMarkerSymbol.SimpleMarkerStyle.Square
},
Label = "Locations"
};
l.Graphics.Add(new Graphic() { Geometry = new MapPoint(-140.9, 63.391, new SpatialReference(4326)) });
MyMap.Layers.Add(l);
}