Amendment to Letter Agreement Regarding Redemption and Exchange of Series Z Preferred Stock between Einstein Noah Restaurant Group Inc. and Halpern Denny III, L.P.

Exhibit 10.01

March 17, 2010

William Nimmo

Halpern Denny III, L.P.

399 Boylston St.

Boston, MA 02116-3338

Redemption of Series Z Preferred Stock (“Series Z Preferred”)

Amendment to Letter Agreement Dated May 27, 2009

Dear Bill:

This letter (the “March Amendment”) amends and supplements the letter agreement dated May 27, 2009 (the “Original Letter Agreement” and together with the March Amendment referred to herein as this “Letter Agreement”) regarding the Corporation’s and Halpern Denny III, L.P.’s (“Halpern Denny”) understanding about the mandatory redemption of the Series Z Preferred after June 30, 2010. Any defined terms used in this letter without definition shall have the meaning set forth in the New World Restaurant Group, Inc. Certificate of Designation, Preferences and Rights of Series Z Preferred Stock dated September 29, 2003 (the “Certificate”).

In connection with the redemption of the Series Z Preferred, the Corporation and Halpern Denny, intending to be legally bound, hereby agree as follows:

a. Pursuant to the mandatory redemption provisions of the Certificate, on or prior to March 31, 2010, the Corporation shall redeem (subject to the legal availability of funds) at least a number of shares of Series Z Preferred equal to $5,000,000 divided by the sum of the Redemption Price of $1,000 per share and the Additional Redemption Price (as defined below) per share as of such redemption date

b. In addition, pursuant to the mandatory redemption provisions of the Certificate, at any time from the date of this letter through June 30, 2011, the Corporation may redeem (subject to the legal availability of funds) as many other shares of Series Z Preferred at the Redemption Price of $1,000 per share plus the Additional Redemption Price per share as of such redemption date.

c. Pursuant to the mandatory redemption provisions of the Certificate, on June 30, 2011, the Corporation shall redeem (subject to the legal availability of funds) all remaining outstanding shares of Series Z Preferred at the Redemption Price of $1,000 per share plus the Additional Redemption Price per share as of such redemption date.

Halpern Denny III, L.P.

March 17, 2010

Page 2

For purposes of this Letter Agreement, the “Additional Redemption Price” shall mean, as of each redemption date, an amount per share of Series Z Preferred equal to the aggregate cumulative dividends which have accrued with respect to the outstanding Liquidation Preference for such share of Series Z Preferred and which dividends remain unpaid as of such redemption date. The amount of such dividends shall be calculated in accordance with Section 4(c)(v) of the Certificate and nothing in this Letter Agreement shall modify the amount of dividends payable to Halpern Denny pursuant to the terms of the Certificate, except as expressly provided in paragraph 2 below.

a. Exchange Option. At any time on or after July 1, 2010, Halpern Denny shall have the option to require the Corporation to exchange 50% of the shares of Series Z Preferred that remain outstanding on June 30, 2010, after any redemptions of the Series Z Preferred made on that date (the “Exchange Shares”) for newly issued, freely tradable shares of common stock of the Corporation (the “Exchange Option”). In order to exercise the Exchange Option, Halpern Denny must provide the Corporation advance written notice of its election to exercise the Exchange Option and must elect to exchange all (and not less than all) of the Exchange Shares that are then outstanding (the “Exchange Notice”). The Corporation shall issue such shares of common stock to Halpern Denny no later than 3 business days after receipt by the Corporation of the Exchange Shares from Halpern Denny. For avoidance of doubt, such shares of common stock shall be immediately available for trading on a national securities exchange or NASDAQ and of the same class of common stock of the Corporation that is registered pursuant to Section 12(b) of the Securities Exchange Act of 1934, such shares shall be issued without any legend restricting the immediate trading of such shares by Halpern Denny and the Corporation shall provide the transfer agent for such common stock any required legal opinion or other documentation to cause such transfer agent to issue such shares to Halpern Denny without such legend. If Halpern Denny desires to transfer such common stock, the Corporation shall cooperate with and use commercially reasonable efforts to assist Halpern Denny with such transfer. Furthermore, for avoidance of doubt, the Exchange Option, if exercised, shall be a stock for stock exchange only and no cash shall be delivered to the Corporation therewith. If Halpern Denny does not exercise the Exchange Option, the Corporation shall continue to be obligated to redeem the Exchange Shares for cash in accordance with the terms of the Certificate and this Letter Agreement.

Halpern Denny III, L.P.

March 17, 2010

Page 3

b. Exchange Price. Upon exercise of the Exchange Option, the amount of shares of common stock of the Corporation to be issued to Halpern Denny shall equal the quotient obtained when (a) is divided by (b), where (a) is the product of the number of Exchange Shares multiplied by the sum of (i) $1,000 per share plus (ii) the Additional Redemption Price per share as of June 30, 2010, and (b) is $11.50 (the “Exchange Price”). The Exchange Price set forth herein shall be subject to appropriate adjustment in the event of stock splits, stock dividends, mergers, recapitalizations or similar transactions affecting the common stock of the Corporation. Before taking any action which would cause an adjustment reducing the Exchange Price below the then par value of the shares of common stock issuable pursuant to the Exchange Option, the Corporation will take such corporate action which may, in the opinion of its counsel, be necessary in order that the Corporation may validly and legally issue fully paid and nonassessable shares of its common stock at such adjusted Exchange Price.

a. Reduction in Number of Exchange Shares. If the Corporation provides Halpern Denny a written Redemption Notice (each such notice, a “Notice of Intent to Redeem”) relating to the redemption of at least 1,000 shares of Exchange Shares pursuant to paragraphs 1(b) or 1(c) above, but the number of Exchange Shares set forth in the Notice of Intent to Redeem is less than one-third of the Exchange Shares that were outstanding on June 30, 2010, Halpern Denny may elect to either (i) exercise the Exchange Option in full or (ii) accept the cash redemption of the Exchange Shares as offered by the Corporation. Halpern Denny has 7 business days from its receipt of such Notice of Intent to Redeem to make such election in writing to the Corporation. If Halpern Denny elects to accept the cash redemption under such circumstances, upon Halpern Denny’s

Halpern Denny III, L.P.

March 17, 2010

Page 4

receipt of the proceeds of such redemption, the Exchange Option shall expire with respect to 50% of the number of Exchange Shares. If Halpern Denny does not make such election in a timely manner, the Corporation will proceed to redeem the Exchange Shares for cash and upon Halpern Denny’s receipt of the proceeds of such redemption, the Exchange Option shall expire with respect to 50% of the number of Exchange Shares.

b. Elimination of Exchange Option. If the Corporation gives Halpern Denny a Notice of Intent to Redeem at least one-third of the Exchange Shares that were outstanding on June 30, 2010 (the “Threshold”) pursuant to paragraphs 1(b) or 1(c) above, Halpern Denny may elect to either (i) exercise the Exchange Option in full or (ii) accept the cash redemption of the Exchange Shares as offered by the Corporation. Halpern Denny has 7 business days from its receipt of such Notice of Intent to Redeem to make such election in writing to the Corporation. If Halpern Denny elects to accept the cash redemption under such circumstances, the number of Exchange Shares shall be reduced to zero. If Halpern Denny does not make such election in a timely manner, the Corporation will proceed to redeem the shares of Series Z Preferred for cash and, upon Halpern Denny’s receipt of the proceeds of such redemption, the Exchange Option shall expire with respect to all remaining Exchange Shares. The Threshold may be met by the Corporation in either (y) one Notice of Intent to Redeem or (z) by combining the number of Exchange Shares previously redeemed by the Corporation under paragraph 3(a) above together with the number of Exchange Shares set forth in the current Notice of Intent to Redeem.

The parties hereto further agree that the March Amendment shall not constitute a waiver of either party’s rights under the Certificate and that the Corporation’s obligation to redeem all outstanding shares of Series Z Preferred in accordance with Section 4(b) of the Certificate remains outstanding, except that if the Corporation makes the payments set forth above, Halpern Denny agrees it has no rights to, and it shall not to take any action to, enforce the mandatory redemption provisions of the Certificate. The parties agree that the March Amendment shall bind any successors to the Corporation and shall extend to Halpern Denny and its past, present and future parents, subsidiaries, affiliates, directors, officers, partners, employees, agents, representatives, and any and all executors, administrators, successors, assigns or heirs. Halpern Denny has not transferred or assigned any causes of action arising from, related to or connected with the mandatory redemption provisions of the Certificate.

The March Amendment is not the Redemption Notice required by the Certificate and the Corporation shall be required to provide the Redemption Notice in accordance with Section 4(c) of the Certificate in advance of any redemption pursuant to the terms of the Certificate.

Halpern Denny III, L.P.

March 17, 2010

Page 5

The Corporation represents and warrants to Halpern Denny that (i) the March Amendment has been duly authorized by all necessary corporate and other action on behalf of the Corporation and (ii) the March Amendment, including the obligation to pay the Additional Redemption Price and issue shares of common stock pursuant to the Exchange Option, will not violate or result in a default under any of the constituent documents of the Corporation or any material agreement or instrument binding the Corporation, including the Credit Agreement. Halpern Denny represents and warrants to the Corporation that (i) the March Amendment has been duly authorized by all necessary limited partnership and other action on behalf of Halpern Denny and (ii) the March Amendment will not violate or result in a default under any of the constituent documents of Halpern Denny or any material agreement or instrument binding Halpern Denny. Each of the Corporation and Halpern Denny represent and warrant to the other party that the March Amendment has been duly executed and delivered by each party, and constitutes a legal, valid and binding obligation of each party, enforceable in accordance with its terms.

The Corporation shall at all times when the Exchange Option shall be outstanding, reserve and keep available out of its authorized but unissued capital stock, for the purpose of effecting the exchange of the Series Z Preferred contemplated by this Letter Agreement, such number of its duly authorized shares of common stock to be issued pursuant to the Exchange Option as shall from time to time be sufficient to effect the exchange of all outstanding Exchange Shares; and if at any time the number of authorized but unissued shares of such common stock shall not be sufficient to effect the exchange of all then outstanding Exchange Shares, the Corporation shall take such corporate action as may be necessary to increase its authorized but unissued shares of such common stock to such number of shares as shall be sufficient for such purposes, including, without limitation, engaging in best efforts to obtain the requisite stockholder approval of any necessary amendment to the Corporation’s Restated Certificate of Incorporation, as amended.

The March Amendment shall be governed by and construed in accordance with the law of the State of Delaware applicable to agreements made and to be performed in Delaware without giving effect to choice of law or conflicts of law principles.

All provisions of the Original Letter Agreement, except as to paragraph 3 of the Original Letter Agreement which is expressly amended by paragraph 1 of the March Amendment, are in full force and effect and are hereby ratified and confirmed by the parties.

Halpern Denny III, L.P.

March 17, 2010

Page 6

Please acknowledge your acceptance of the terms of the March Amendment by executing it in the space provided below and returning a copy to us.

Accepted And Agreed: