AMENDED AND RESTATED MANAGEMENT CONSULTING AGREEMENT

EXHIBIT 10.13

AMENDED AND RESTATED MANAGEMENT CONSULTING AGREEMENT

This Amended and Restated Management Consulting Agreement (the “Agreement”) is made as of June     , 2004, by and Dex Media East LLC, a Delaware limited liability company (the “Company”), and TC Group, LLC, a Delaware limited liability company (“Carlyle”).

RECITALS:

WHEREAS, Carlyle and the Company are each parties to that certain management consulting and advisory agreement, dated as of November 8, 2002, between the Company and Carlyle (the “Original Management Consulting Agreement”); and

WHEREAS, the Company and Carlyle desire to amend and restate the Original Management Consulting Agreement as set forth herein.

AGREEMENT:

NOW, THEREFORE, in consideration of the foregoing recitals and the covenants and conditions herein set forth, the parties hereto agree as follows:

The Company hereby appoints Carlyle to render the advisory and consulting services described in Section 2 hereof for the term of this Agreement.

During the term of this Agreement, Carlyle shall render to the Company, by and through such of Carlyle’s officers, employees, agents, representatives and affiliates as Carlyle in its sole discretion, shall designate, Financial Advisory Services. “Financial Advisory Services” means financial advisory or any other services rendered by Carlyle to the Company in connection with any acquisitions and divestitures by the Company or any of its subsidiaries, including, without limitation, the sale of substantially all or any portion of the assets of the Company, whether by a sale of assets, the equity interests of the Company, merger or otherwise, and the acquisition or sale of any subsidiary, division or service area of the Company, or the public or private sale of debt or equity interests of the Company, or any of its affiliates or any similar financing transactions.

(a) As consideration for the termination of Carlyle’s Oversight Services (as defined in the Original Management Consulting Agreement) contemplated by

Section 2(a) of the Original Management Consulting Agreement, the Company agrees to pay to Carlyle the sum of $5,000,000, payable in cash on the date hereof.

(b) In consideration of any Financial Advisory Services provided to the Company, Carlyle shall be entitled to receive additional reasonable compensation as agreed upon by the parties hereto and approved by a majority of the members of the board of directors of the Company.

In addition to the compensation payable to Carlyle pursuant to Section 3 hereof, the Company shall, at the direction of Carlyle, pay directly, or reimburse Carlyle for, its reasonable Out-of-Pocket Expenses. For the purposes of this Agreement, the term “Out-of-Pocket Expenses” shall mean the amounts actually paid by Carlyle in cash in connection with its performance of the Financial Advisory Services, including, without limitation, reasonable (i) fees and disbursements (including underwriting fees) of any independent auditors, outside legal counsel, consultants, investment bankers, financial advisors and other independent professionals and organizations, (ii) costs of any outside services or independent contractors such as financial printers, couriers, business publications or similar services and (iii) transportation, per diem, telephone calls, word processing expenses or any similar expense not associated with its ordinary operations. All reimbursements for Out-of-Pocket Expenses shall be made promptly upon or as soon as practicable after presentation by Carlyle to the Company of the statement in connection therewith.

The Company will indemnify and hold harmless Carlyle and its officers, employees, agents, representatives, members and affiliates (each being an “Indemnified Party”) from and against any and all losses, costs, expenses, claims, damages and liabilities (the “Liabilities”) to which such Indemnified Party may become subject under any applicable law, or any claim made by any third party, or otherwise, to the extent they relate to or arise out of the performance of the Financial Advisory Services contemplated by this Agreement or the engagement of Carlyle pursuant to, and the performance by Carlyle of the Financial Advisory Services contemplated by, this Agreement. The Company will reimburse any Indemnified Party for all reasonable costs and expenses (including reasonable attorneys’ fees and expenses) as they are incurred in connection with the investigation of, preparation for or defense of any pending or threatened claim for which the Indemnified Party would be entitled to indemnification under the terms of the previous sentence, or any action or proceeding arising therefrom, whether or not such Indemnified Party is a party hereto, provided that, subject to the following sentence, the Company shall be entitled to assume the defense thereof at its own expense, with counsel satisfactory to such Indemnified Party in its reasonable judgment. Any Indemnified Party may, at its own expense, retain separate counsel to participate in such defense, and in any action, claim or proceeding in which the Company, on the one hand, and an Indemnified Party, on the other hand, is, or is reasonably likely to become, a party, such Indemnified Party shall have the right to employ separate counsel at the Company’s expense and to control its own defense of such action,

claim or proceeding if, in the reasonable opinion of counsel to such Indemnified Party, a conflict or potential conflict exists between the Company, on the one hand, and such Indemnified Party, on the other hand, that would make such separate representation advisable. The Company agrees that it will not, without the prior written consent of the applicable Indemnified Party, settle, compromise or consent to the entry of any judgment in any pending or threatened claim, action or proceeding relating to the matters contemplated hereby (if any Indemnified Party is a party thereto or has been actually threatened to be made a party thereto) unless such settlement, compromise or consent includes an unconditional release of the applicable Indemnified Party and each other Indemnified Party from all liability arising or that may arise out of such claim, action or proceeding. Provided that the Company is not in breach of its indemnification obligations hereunder, no Indemnified Party shall settle or compromise any claim subject to indemnification hereunder without the consent of the Company. The Company will not be liable under the foregoing indemnification provision to the extent that any loss, claim, damage, liability, cost or expense is determined by a court, in a final judgment from which no further appeal may be taken, to have resulted solely from the gross negligence or willful misconduct of Carlyle. If an Indemnified Party is reimbursed hereunder for any expenses, such reimbursement of expenses shall be refunded to the extent it is finally judicially determined that the Liabilities in question resulted solely from the gross negligence or willful misconduct of Carlyle.

This Agreement shall be in effect on the date hereof and shall continue until such time as Carlyle or one or more of its affiliates collectively control, in the aggregate, less than 10% of the equity interests of the Company, or such earlier time as the Company and Carlyle may mutually agree. The provisions of Sections 5 and 8 and otherwise as the context so requires shall survive the termination of this Agreement.

Nothing herein shall in any way preclude Carlyle or its officers, employees, agents, representatives, members or affiliates from engaging in any business activities or from performing services for its own account or for the account of others, including for companies that may be in competition with the business conducted by the Company.

(a) No amendment or waiver of any provision of this Agreement, or consent to any departure by either party from any such provision, shall be effective unless the same shall be in writing and signed by the parties to this Agreement, and, in any case, such amendment, waiver or consent shall be effective only in the specific instance and for the specific purpose for which given.

(b) This Agreement and the rights of the parties hereunder may not be assigned without the prior written consent of the parties hereto; provided, however, that Carlyle may, at its sole discretion, assign or transfer its duties or interests hereunder to its affiliates.

(c) Any and all notices hereunder shall, in the absence of receipted hand delivery, be deemed duly given when mailed, if the same shall be sent by registered or certified mail, return receipt requested, and the mailing date shall be deemed the date from which all time periods pertaining to a date of notice shall run. Notices shall be addressed to the parties at the following addresses:

(d) This Agreement shall constitute the entire agreement between the parties with respect to the subject matter hereof, and shall supersede all previous oral and written (and all contemporaneous oral) negotiations, commitments, agreements and understandings relating hereto.

(e) This Agreement shall be governed by, and enforced in accordance with, the laws of the State of New York (excluding the choice of law principles thereof). Each of the parties hereby irrevocably and unconditionally consents to submit to the exclusive jurisdiction of the courts of the State of New York and of the United States of America, in each case located in the County of New York, in any action or proceeding arising out of or relating to this Agreement. This Agreement shall inure to the benefit of, and be binding upon, Carlyle and the Company (including any present or future subsidiaries of the Company that are not signatories hereto), and their respective successors and assigns.

(f) This Agreement may be executed in multiple counterparts, and by different parties on separate counterparts. Each set of counterparts showing execution by all parties shall be deemed an original, and shall constitute one and the same instrument.

(g) The waiver by any party of any breach of this Agreement shall not operate as or be construed to be a waiver by such party of any subsequent breach.

[signature page to follow]

IN WITNESS WHEREOF, the parties have caused this Agreement to be executed and delivered by their duly authorized officers or agents as set forth below.