グラフの名前はNameプロパティです。次のマクロは、アクティブシートのグラフに新しい名前を設定しています。
Sub Sample()
With ActiveSheet.ChartObjects(1)
.Name = "俺のグラフ1"
MsgBox .Name & vbCrLf & _
.Chart.Name
End With
End Sub

ワークシート上の埋め込みグラフは、おおむね次のようなオブジェクト構造になっています。

グラフの本体はChartオブジェクトで、グラフを描画する枠のようなものがChartObjectオブジェクトです。埋め込みグラフを削除したり移動したりするときは、ChartObjectオブジェクトの方を操作してやります。また、系列やタイトルやデータラベルなどグラフのパーツを操作するためにChartオブジェクトを特定する場合も「ChartObject(1).Chart」のようにChartObjectオブジェクトから降りてやります。
なので、グラフの名前を設定したり取得したりするときは、ChartObjectオブジェクトのNameプロパティが重要になってきます。上記マクロで試したように、ChartオブジェクトにもNameプロパティがありますが、Chartオブジェクトの名前を管理しなければならないのは、希なケースといえるでしょう。
ちなみに、ChartオブジェクトのNameプロパティは値の取得のみ可能です。設定することはできません。設定しようとすると、下記のようなエラーになります。
Sub Sample()
With ActiveSheet.ChartObjects(1)
.Name = "俺のグラフ1"
.Chart.Name = "私のグラフ1"
MsgBox .Name & vbCrLf & _
.Chart.Name
End With
End Sub

なぜ「メモリが不足しています」エラーになるんだろう?読み取り専用プロパティに値を設定しようとしたのだから、実行時エラー387の「プロパティは値を設定できません」っていうエラーだったら分かりやすいのに。
Excel 2003で、グラフの名前を設定したり取得するときも、下記のマクロを使います。
Sub Sample()
With ActiveSheet.ChartObjects(1)
.Name = "俺のグラフ1"
MsgBox .Name & vbCrLf & _
.Chart.Name
End With
End Sub
ちなみに、実行すると次のようになります。

細かいところですが、ここもExcel 2003とExcel 2007で変わっていますね。Chartオブジェクトの名前(Name)は、Excel 2003では「ブック名 グラフ名」なのに対して、Excel 2007では「シート名 グラフ名」に変わっています。まぁ、前述したように、Chartオブジェクトの名前をどうとかすることは希でしょうから、大きな問題ではないでしょう。ついでに、Excel 2003でも、読み取り専用のChart.Nameプロパティに値を設定してみましょう。エラーになるはずです。

こっちは1004ですか。どっちにしても、分かりにくいですね。
【Excel 2007での実行結果】
なんか、検証の方法が逆になってしまいましたが、ChartObjectオブジェクトのNameプロパティに関して、互換性は大丈夫のようです。