R.R. Donnelley & Sons Company 111 South Wacker Drive

Exhibit 10.25

R.R. Donnelley & Sons Company

111 South Wacker Drive

Chicago, IL 60606-4301

Amended and Restated as of May 8, 2007

Mr. John Paloian

[address]

Dear John:

The purpose of this letter is to amend and restate in its entirety the Employment Agreement, dated as of March 25, 2004, between you and R.R. Donnelley & Sons Company (the “Company”). You are currently the Group President, RR Donnelley Global Print Solutions of the Company and, effective as of the date hereof, you shall serve as Chief Operating Officer of the Company in accordance with the terms and provisions of this Agreement as well as any employment and other policies applicable to employees of the Company and its subsidiaries from time to time during the term of your employment. All capitalized terms used but not defined in the text of this letter shall have the meanings assigned to such terms in Annex A.

We and you hereby acknowledge that your employment with the Company constitutes “at-will” employment and that either party may terminate this Agreement at any time, upon written notice of termination within a reasonable period of time before the effective date of the termination. With respect to the terms of your employment with the Company, you will have the customary duties, responsibilities and authorities of a chief operating officer at a corporation of a similar size and nature. You will report to the Chief Executive Officer of the Company (the “CEO”). You will receive such office, staffing and other assistance as is commensurate with that received by other senior executive officers at your level at a corporation of similar size and nature.

I. Compensation

You will receive the following compensation and benefits, from which the Company may withhold any amounts required by applicable law:

(i) The Company will pay you a base salary (“Base Salary”) at the rate of $700,000 per year. This Base Salary will be paid in accordance with the normal payroll practices of the Company.

(ii) You will be eligible to receive an annual bonus (the “Annual Bonus”) at a target level of 150% of Base Salary in respect of each fiscal year of the Company in accordance with the Company’s annual incentive compensation plan and payable if the Company achieves the performance objectives set forth by the Board of Directors (the “Board”) (or any designated committee thereof) from time to time. These performance objectives will be communicated to you no later than April 1^st of each year. The Annual Bonus shall be approved by the Board.

(iii) In addition, you will continue to be eligible to participate in any nonqualified pension plans and qualified plans in the same manner as you currently participate or may elect to participate from time to time after the date of this Agreement.

(iv) You shall be eligible for four (4) weeks vacation annually.

(v) You shall be eligible for a car allowance pursuant to policies applicable to senior officers of the Company from time to time during the term of your employment.

(vi) You shall be eligible for an allowance for financial planning (including tax advice and legal fees related thereto) pursuant to policies applicable to senior officers of the Company from time to time during the term of your employment.

(vii) You shall be eligible for supplemental term life insurance benefits and supplemental long-term disability benefits pursuant to policies applicable to senior officers of the Company ( but no less than $2,000,000) from time to time during the term of your employment, provided that you are insurable in accordance with standard underwriting requirements (including passing any physical exams and providing any information necessary to obtain such insurance coverage).

(viii) On March 21, 2007, the Company granted to you, under the R.R. Donnelley & Sons Company 2004 Performance Incentive Plan, the following: 30,000 Performance Share Units (pursuant to which grant if certain performance targets are achieved the amount payable could reach 250% of the initial award) and options to purchase 130,000 shares of common stock of the Company. It is the Company’s current intention that annual equity grants will be made to you in each of 2008 and 2009 that will, at a minimum, be consistent with the levels granted in the Performance Unit Award and Stock Option Agreement awarded March 21, 2007.

II. Severance

(i) Termination Not Following a Change in Control

If, prior to a Change in Control, the Company terminates your employment as Chief Operating Officer without Cause or if you terminate your employment for Good Reason:

(A) the Company will pay you an amount equal to two times your Annualized Total Compensation, subject to the execution by you of a customary release, which amount shall be payable in equal installments over the twenty-four (24) months following the date your employment with the Company is terminated (the “Termination Date”);

(B) the Company will provide to you a continuation of all benefits, including a car allowance and other related benefits, if any, which you were eligible to receive immediately prior to such termination, for the twenty-four (24) months following the Termination Date; and

2

(C) all outstanding stock options, restricted stock or restricted stock unit awards or other equity grants (other than performance shares or performance share units) issued to you will vest 100% immediately as of the Termination Date.

Upon any termination of your employment prior to a Change in Control, any performance shares or performance share units will vest in accordance with the applicable award agreement. Your rights of indemnification under the Company’s and any of its subsidiaries organizational documents, any plan or agreement at law or otherwise and your rights thereunder to director’s and officer’s liability insurance coverage for, in both cases, actions as an officer and director of the Company and its affiliates shall survive any termination of your employment. In the event of any termination, you agree to resign as an officer and director of the Company and its subsidiaries and affiliates.

(ii) Termination Following a Change in Control

If, following a Change in Control, the Company terminates your employment as Chief Operating Officer without Cause or if you terminate your employment for Good Reason:

(A) the Company will pay you an amount equal to three times your Annualized Total Compensation, subject to the execution by you of a customary release, which amount shall be paid to you in a lump sum as soon as is reasonably practicable following the Termination Date;

(B) the Company will provide to you a continuation of all benefits, including a car allowance and other related benefits, if any, which you were eligible to receive immediately prior to such termination, for the thirty-six (36) months following the Termination Date;

(C) the Company will make the additional payments provided in Annex B, if applicable;

(D) all outstanding stock options, restricted stock or restricted stock unit awards or other equity grants (other than performance shares or performance share units) issued to you will vest 100% immediately as of the Termination Date and any performance shares or performance share units will vest in accordance with the applicable award agreement; and

(E) you shall be entitled to a pro rata bonus under the Company’s annual bonus program in effect for the year in which the Termination Date occurs, which pro rata bonus shall be paid at the same time as annual bonuses for such year are paid to the Company’s senior executives and shall be equal to the amount, if any, which you would have received under such plan (without regard to any executive-specific objectives), on the basis of the Company’s actual performance for the year, had your employment not terminated, multiplied by a fraction, the numerator of which is the number of days in the year elapsed prior to the Termination Date and the denominator of which is 365.

Your rights of indemnification under the Company’s and any of its subsidiaries organizational documents, any plan or agreement at law or otherwise and your rights thereunder to director’s and officer’s liability insurance coverage for, in both cases, actions as an officer and director of the Company and its affiliates shall survive any termination of your employment. In the event of any termination, you agree to resign as an officer and director of the Company and its subsidiaries and affiliates.

3

Notwithstanding the foregoing, any termination by the Company without Cause or termination by you for Good Reason which takes place within six (6) months prior to a Change in Control, shall be, presumptively, a termination following a Change in Control.

III. Compliance with Section 409A of the Internal Revenue Code.

All payments and benefits pursuant to this letter shall be subject to the provisions of this Section III. If you are a “Specified Employee” of the Company for purposes of Internal Revenue Code Section 409A (“Code Section 409A”) at the time of a payment event set forth in this letter, then no severance or other payments or benefits pursuant to this letter shall be made to you by the Company until the amount of time has passed that is necessary to avoid incurring excise taxes under Code Section 409A. Should this Section III result in a delay of payments to you, on the first day any such payments may be made without incurring a penalty pursuant to Code Section 409A (the “409A Payment Date”), the Company shall begin to make such payments as provided for in this letter, provided that any amounts that would have been payable earlier but for the application of this Section III, shall be paid in lump-sum on the 409A Payment Date. For purposes of this provision, the term Specified Employee shall have the meaning set forth in Section 409A(2)(B)(i) of the Internal Revenue Code of 1986, as amended or any successor provision and the treasury regulations and rulings issued thereunder. If any compensation or benefits provided by this letter may result in the application of Code Section 409A, the Company shall, in consultation with you, modify this letter in the least restrictive manner necessary in order to exclude such compensation from the definition of “deferred compensation” within the meaning of such Code Section 409A or in order to comply with the provisions of Code Section 409A of the Code and without any diminution in the value of the payments or benefits to you.

IV. General

You agree (i) that at all times both during and after your employment, you will respect the confidentiality of Company’s and its subsidiaries and affiliates’ confidential information and will not disparage the Company and its subsidiaries and affiliates or their officers, directors or employees, and (ii) during your employment and for twenty-four (24) months thereafter, you will not (a) accept a position with, or provide material services to, an entity that competes with a portion of the Company’s business representing more than $25 million of the Company’s revenues on the date of your departure, (b) solicit or hire, or assist others in the solicitation or hiring of, the Company’s employees or (c) interfere with the Company’s business relationships with any material customers or suppliers.

All notices or communications under this Agreement must be in writing, addressed; (i) if to the Company, to the attention of the Chief Human Resources Officer at the Company’s address first written above and (ii) if to you, at your address first written above (or to any other addresses as either party may designate in a notice duly delivered as described in this paragraph). Any notice or communication shall be delivered by telecopy, by hand or by courier. Notices and communications may also be sent by certified or registered mail, return receipt requested, postage prepaid, addressed as above and Notice shall be effective upon the actual receipt of

4

notice by the recipient thereof. Any controversy or claim arising out of or relating to this Agreement or the breach of this Agreement that cannot be resolved by you and the Company, including any dispute as to the calculation of any payments hereunder, and the terms of this Agreement, shall be determined by a single arbitrator in New York, NY, in accordance with the rules of the American Arbitration Association. The decision of the arbitrator shall be final and binding and may be entered in any court of competent jurisdiction. The arbitrator may award the party he determines has prevailed in the arbitration any legal fees and other fees and expenses that may be incurred in respect of enforcing its respective rights under this Agreement. This Agreement shall be interpreted in accordance with the laws of the State of New York.

This Agreement sets forth the entire agreement between us with respect to the matters set forth herein, and fully supersedes any prior agreements or understandings between us. This Agreement may be executed in counterparts. This Agreement may not be modified or terminated orally.

If the foregoing terms and conditions are acceptable and agreed to by you, please sign on the line provided below to signify such acceptance and agreement and return the executed copy to the Chief Human Resources Officer of the Company, at the Company’s address first written above.

Accepted and Agreed as of this 8th day of May, 2007

5

Annex A

Definitions

a. “Annualized Total Compensation” means Base Salary plus Annual Bonus (as if all necessary targets and objectives were met at target level) for one year at the rate in effect immediately before the Termination Date.

b. “Cause” means (i) the willful and continued failure of Executive to perform substantially his duties with the Company (other than any such failure resulting from Executive’s incapacity due to physical or mental illness or any such failure subsequent to Executive being delivered a notice of termination without Cause by the Company or delivering a notice of termination for Good Reason to the Company) after a written demand for substantial performance is delivered to Executive by the CEO, the Chairman or the Board that specifically identifies the manner in which the CEO, the Chairman or the Board believes that Executive has not substantially performed Executive’s duties, (ii) the willful engaging by Executive in illegal conduct or misconduct which is demonstrably and materially injurious (monetarily or otherwise) to the Company or its subsidiaries and affiliates, (iii) conviction of or the pleading of nolo contendere with regard to, a felony or any crime involving fraud, dishonesty or moral turpitude, or (iv) refusal or failure to attempt in good faith to follow the written direction of the CEO, the Chairman or the Board (provided that such written direction is consistent with Executive’s duty and station) promptly upon receipt of such written direction. A termination for Cause after a Change in Control shall be based only on events occurring after such Change in Control; provided, however, the foregoing limitation shall not apply to an event constituting Cause which was not discovered by the Company prior to a Change in Control. For purpose of this paragraph (a), no act or failure to act by Executive shall be considered “willful” unless done or omitted to be done by Executive in bad faith and without reasonable belief that Executive’s action or omission was in the best interests of the Company or its subsidiaries and affiliates. Any act, or failure to act, based upon authority given pursuant to a resolution duly adopted by the Board or based upon the advice of counsel for the Company shall be conclusively presumed to be done, or omitted to be done, by Executive in good faith and in the best interests of the Company. Notwithstanding the foregoing, the Company shall provide Executive a reasonable amount of time, after a notice and demand for substantial performance is delivered to Executive, to cure any failure to perform, and if such failure is so cured within a reasonable amount of time thereafter, such failure shall not be deemed to have occurred.

c. “Change in Control” means the occurrence of any one of the following events:

(i) individuals who, on the date of this Agreement, constitute the Board (the “Incumbent Directors”) cease for any reason to constitute at least a majority of the Board, provided that any person becoming a director subsequent to the date of this Agreement, whose election or nomination for election was approved by a vote of at least two-thirds of the Incumbent Directors then on the Board (either by a specific vote or by approval of the proxy statement of the Company in which such person is named as a nominee for director, without written objection to such nomination) shall be an Incumbent Director; provided, however, that no individual initially elected or nominated as a director of the Company as a result of an actual or threatened election contest with respect to directors or as a result of any other actual or threatened solicitation of proxies or consents by or on behalf of any person other than the Board shall be deemed to be an Incumbent Director;

6

(ii) any “person” (as such term is defined in Section 3(a)(9) of the Securities Exchange Act of 1934 (the “Exchange Act”) and as used in Sections 13(d)(3) and 14(d)(2) of the Exchange Act) is or becomes a “beneficial owner” (as defined in Rule 13d-3 under the Exchange Act), directly or indirectly, of securities of the Company representing 35% or more of the combined voting power of the Company’s then outstanding securities eligible to vote for the election of the Board (the “Company Voting Securities”); provided, however, that the event described in this paragraph (ii) shall not be deemed to be a Change in Control by virtue of any of the following acquisitions: (A) by the Company or any subsidiary, (B) by any employee benefit plan (or related trust) sponsored or maintained by the Company or any subsidiary, (C) by any underwriter temporarily holding securities pursuant to an offering of such securities, or (D) pursuant to a Non-Qualifying Transaction (as defined in paragraph (iii);

(iii) the consummation of a merger, consolidation, statutory share exchange or similar form of corporate transaction involving the Company or any of its Subsidiaries that requires the approval of the Company’s stockholders, whether for such transaction or the issuance of securities in the transaction (a “Business Combination”), unless immediately following such Business Combination: (A) more than 50% of the total voting power of (x) the corporation resulting from such Business Combination (the “Surviving Corporation”), or (y) if applicable, the ultimate parent corporation that directly or indirectly has beneficial ownership of 100% of the voting securities eligible to elect directors of the Surviving Corporation (the “Parent Corporation”), is represented by Company Voting Securities that were outstanding immediately prior to such Business Combination (or, if applicable, is represented by shares into which such Company Voting Securities were converted pursuant to such Business Combination), and such voting power among the holders thereof is in substantially the same proportion as the voting power of such Company Voting Securities among the holders thereof immediately prior to the Business Combination, (B) no person (other than any employee benefit plan (or related trust) sponsored or maintained by the Surviving Corporation or the Parent Corporation), is or becomes the beneficial owner, directly or indirectly, of 35% or more of the total voting power of the outstanding voting securities eligible to elect directors of the Parent Corporation (or, if there is no Parent Corporation, the Surviving Corporation) other than persons set forth in (A) through (F) of paragraph (ii) and (C) at least a majority of the members of the board of directors of the Parent Corporation (or, if there is no Parent Corporation, the Surviving Corporation) following the consummation of the Business Combination were Incumbent Directors at the time of the Board’s approval of the execution of the initial agreement providing for such Business Combination (any Business Combination which satisfies all of the criteria specified in (A), (B) and (C) above shall be deemed to be a “Non-Qualifying Transaction”);

(iv) the closing of a sale of all or substantially all of the Company’s assets, other than to an entity or in a manner where the voting securities immediately prior to such sale represent directly or indirectly after such sale at least 50% of the voting securities of the entity acquiring such assets in approximately the same proportion as prior to such sale; or

(v) the stockholders of the Company approve a plan of complete liquidation or dissolution of the Company.

7

Notwithstanding the foregoing, a Change in Control of the Company shall not be deemed to occur solely because any person acquires beneficial ownership of more than 35% of the Company Voting Securities as a result of the acquisition of Company Voting Securities by the Company which reduces the number of Company Voting Securities outstanding; provided, that if after such acquisition by the Company such person becomes the beneficial owner of additional Company Voting Securities that increases the percentage of outstanding Company Voting Securities beneficially owned by such person, a Change in Control of the Company shall then occur.

d. “Good Reason” means, without Executive’s express written consent, the occurrence of any of the following events:

(i) a change in the Executive’s duties or responsibilities (including reporting responsibilities) that taken as a whole represents a material and adverse diminution of the Executive’s duties, responsibilities or status with the Company (other than a temporary change that results from or relates to the incapacitation of the Executive due to physical or mental illness);

(ii) a reduction by the Company in Executive’s rate of annual base salary or annual target bonus opportunity (including any material and adverse change in the formula for such annual bonus target) as the same may be increased from time to time thereafter;

(iii) any requirement of the Company that Executive’s office be more than seventy-five (75) miles from Executive’s place of residence as of the date of this Agreement; or

(iv) any material breach of the Agreement by the Company.

Notwithstanding the foregoing, a Good Reason event shall not be deemed to have occurred if the Company cures such action, failure or breach within ten (10) days after receipt of notice thereof given by Executive. Executive’s right to terminate employment for Good Reason shall not be affected by Executive’s incapacities due to mental or physical illness and Executive’s continued employment shall not constitute consent to, or a waiver of rights with respect to, any event or condition constituting Good Reason; provided, however, that Executive must provide notice of termination of employment within ninety (90) days following Executive’s knowledge of an event constituting Good Reason or such event shall not constitute Good Reason under this Agreement.

8

Annex B

Gross-Up Payments

(a) Anything in this Agreement to the contrary notwithstanding, in the event it shall be determined that any payment, award, benefit or distribution (or any acceleration of any payment, award, benefit or distribution) by the Company (or any of its affiliated entities) or any entity which effectuates a Change in Control (or any of its affiliated entities) to or for the benefit of Executive (whether pursuant to the terms of this Agreement or otherwise, but determined without regard to any additional payments required under this Annex B) (the “Payments”) would be subject to the excise tax imposed by Section 4999 of the Internal Revenue Code of 1986, as amended (the “Code”), or any interest or penalties are incurred by Executive with respect to such excise tax (such excise tax, together with any such interest and penalties, are hereinafter collectively referred to as the “Excise Tax”), then the Company shall pay to Executive an additional payment (a “Gross-Up Payment”) in an amount such that after payment by Executive of all taxes (including any Excise Tax) imposed upon the Gross-Up Payment, Executive retains an amount of the Gross-Up Payment equal to the Excise Tax imposed upon the Payments. For purposes of determining the amount of the Gross-up Payment, the Executive shall be deemed to (i) pay federal income taxes at the highest marginal rates of federal income taxation for the calendar year in which the Gross-up Payment is to be made, and (ii) pay applicable state and local income taxes at the highest marginal rate of taxation for the calendar year in which the Gross-up Payment is to be made, net of the maximum reduction in federal income taxes which could be obtained from deduction of such state and local taxes. Notwithstanding the foregoing provisions of this Annex B, if it shall be determined that Executive is entitled to a Gross-Up Payment, but that the Payments would not be subject to the Excise Tax if the Payments were reduced by an amount that is less than 10% of the portion of the Payments that would be treated as “parachute payments” under Section 280G of the Code, then the amounts payable to Executive under this Agreement shall be reduced (but not below zero) to the maximum amount that could be paid to Executive without giving rise to the Excise Tax (the “Safe Harbor Cap”), and no Gross-Up Payment shall be made to Executive. The reduction of the amounts payable hereunder, if applicable, shall be made by reducing first the payments under Section I(a)(ii), unless an alternative method of reduction is elected by Executive. For purposes of reducing the Payments to the Safe Harbor Cap, only amounts payable under this Agreement (and no other Payments) shall be reduced. If the reduction of the amounts payable hereunder would not result in a reduction of the Payments to the Safe Harbor Cap, no amounts payable under this Agreement shall be reduced pursuant to this provision.

(b) Subject to the provisions of paragraph (a) of this Annex B, all determinations required to be made under this Annex B, including whether and when a Gross-Up Payment is required, the amount of such Gross-Up Payment, the reduction of the Payments to the Safe Harbor Cap and the assumptions to be utilized in arriving at such determinations, shall be made by the public accounting firm that is retained by the Company as of the date immediately prior to the Change in Control (the “Accounting Firm”) which shall provide detailed supporting calculations both to the Company and Executive within fifteen (15) business days of the receipt of notice from the Company or the Executive that there has been a Payment, or such earlier time as is requested by the Company (collectively, the “Determination”). In the event that the Accounting Firm is serving as accountant or auditor for the individual, entity or group effecting the Change in

9

Control, Executive may appoint another nationally recognized public accounting firm to make the determinations required hereunder (which accounting firm shall then be referred to as the Accounting Firm hereunder). All fees and expenses of the Accounting Firm shall be borne solely by the Company and the Company shall enter into any agreement requested by the Accounting Firm in connection with the performance of the services hereunder. The Gross-up Payment under this Annex B with respect to any Payments shall be made no later than thirty (30) days following such Payment. If the Accounting Firm determines that no Excise Tax is payable by Executive, it shall furnish Executive with a written opinion to such effect, and to the effect that failure to report the Excise Tax, if any, on Executive’s applicable federal income tax return will not result in the imposition of a negligence or similar penalty. In the event the Accounting Firm determines that the Payments shall be reduced to the Safe Harbor Cap, it shall furnish Executive with a written opinion to such effect. The Determination by the Accounting Firm shall be binding upon the Company and Executive. As a result of the uncertainty in the application of Section 4999 of the Code at the time of the Determination, it is possible that Gross-Up Payments which will not have been made by the Company should have been made (“Underpayment”) or Gross-up Payments are made by the Company which should not have been made (“Overpayment”), consistent with the calculations required to be made hereunder. In the event that the Executive thereafter is required to make payment of any Excise Tax or additional Excise Tax, the Accounting Firm shall determine the amount of the Underpayment that has occurred and any such Underpayment (together with interest at the rate provided in Section 1274(b)(2)(B) of the Code) shall be promptly paid by the Company to or for the benefit of Executive. In the event the amount of the Gross-up Payment exceeds the amount necessary to reimburse the Executive for his Excise Tax, the Accounting Firm shall determine the amount of the Overpayment that has been made and any such Overpayment (together with interest at the rate provided in Section 1274(b)(2) of the Code) shall be promptly paid by Executive (to the extent he has received a refund if the applicable Excise Tax has been paid to the Internal Revenue Service) to or for the benefit of the Company. Executive shall cooperate, to the extent his expenses are reimbursed by the Company, with any reasonable requests by the Company in connection with any contests or disputes with the Internal Revenue Service in connection with the Excise Tax and the Executive shall permit the Company to control issues related to the Excise Tax (at its expense) to permit a representative of the Company to accompany the Executive to any conference with any taxing authority and to promptly deliver to the Company copies of any written communications and summaries of any verbal communications with any taxing authority regarding the Excise Tax.

10