Exhibit 10.4
                                                                   ------------

                                                600 Lexington Avenue, 6th Floor
                                                New York, New York
                                                Phone: (212) 759-4433
                                                Fax:   (972) 281-5831

                                                www.alvarezandmarsal.com


[ALVAREZ & MARSAL GRAPHIC OMITTED]
- -------------------------------------------------------------------------------



August 15, 2005



Ms. Chris Davis
Chairman of the Board of Directors
McLeodUSA, Inc.
6400 C Street SW
Cedar Rapids, Iowa  52406


Dear Ms. Davis:

This letter confirms, amends and restates the letter agreement dated March 29,
2005 between Alvarez & Marsal, LLC ("A&M") and McLeodUSA, Inc. (the "Company")
(as amended and restated "this Agreement"). Upon execution of this letter by
each of the parties below, this letter will constitute an agreement between the
Company and A&M. A&M shall continue to hold the retainer previously delivered
on the terms and conditions set forth herein.


         1.       Officers

                  In connection with this agreement A&M shall make available to
                  the Company:

                  (a)      Stan Springel to serve as the Chief Restructuring
                           Officer of the Company (the "CRO") and

                  (b)      Jay Bradford, Girish Satya, Kevin Hausler, Joseph
                           Bondi, Biff McGuire and Arnold Adams (collectively,
                           with the CRO, the `Officers" and each of the
                           Officers individually, an "Officer") as well, upon
                           the mutual agreement of A&M and the Company's Board
                           of Directors, such additional personnel as are
                           necessary to assist in the performance of the duties
                           set forth in the clause 2 below (the "Additional
                           Officers"). Each of the Officers and any Additional
                           Officers shall be designated by the Company as
                           executive officers. In addition to the Officers, A&M
                           may make available to the Company additional
                           personnel who will serve as consultants to the
                           Company on a specific project basis ("Consultants").

         2.       Duties:

                  It is anticipated that the Officers' activities shall include
                  the following:

                  (a)      Assist the Company in its overall reorganization
                           efforts.

                  (b)      Assist the Company in the development of a business
                           plan that may be utilized in part of a
                           reorganization plan.

                  (c)      Assist the Company on financing issues including
                           cash management support, assistance in preparation
                           of analytical reports and liaison with the Company's
                           creditors; and

                  (e)      Assist the Company in cost reduction activities and
                           the sale of non-core assets; and

                  (f)      Assist the Company in developing employee retention
                           programs; and

                  (g)      Other activities as are approved by you or the Board
                           of Directors and agreed to by A&M.

                           You understand that the services to be rendered by
                           the Officers and Consultants may include the
                           preparation of projections and other forward-looking
                           statements, and numerous factors can affect the
                           actual results of the Company's operations, which
                           may materially and adversely differ from those
                           projections. In addition, the Officers and
                           Consultants will be relying on information provided
                           by the Company in the preparation of those
                           projections and other forward-looking statements.
                           Neither A&M nor any of the Officers or Consultants
                           make any representation or guarantee that an
                           appropriate restructuring proposal can be formulated
                           for the Company, that restructuring is the best
                           course of action for the Company or, if formulated,
                           that any proposed restructuring plan will be
                           accepted by the Company's creditors, shareholders
                           and other constituents. Further, neither A&M nor the
                           Officers or Consultants assume any responsibility
                           for the implementation or selection of any
                           restructuring proposal which they assist the Company
                           in formulating.

                           In rendering services to the Company, the Officers
                           will report directly to the Board of Directors and
                           will make recommendations to and consult with the
                           Board of Directors.

         3.       Stan Springel, a Managing Director of A&M, will be
                  responsible for the overall engagement. He will be assisted
                  by Jay Bradford, a Director of A&M on a fulltime basis and
                  Kevin Hausler, a contractor to A&M on a part-time basis; as
                  well as other A&M personnel as necessary, provided they are
                  approved in advance by the Company. Joe Bondi will provide
                  assistance from time to time as required by A&M and as
                  requested by the Company.

         4.       Employment by A&M:

                  The CRO and the Officers (and any Consultants) shall continue
                  to be employed by A&M (or in the case of Kevin Hausler, be a
                  contractor to A&M) and while rendering services to the
                  Company will continue to work with other personnel at A&M in
                  connection with unrelated matters, which shall not interfere
                  with services pursuant to this agreement. With respect to the
                  Company, however the Officers and Consultants shall operate
                  under the direction of the Board of Directors and A&M shall
                  have no liability to the Company for any acts or omissions of
                  such Officers.

         5.       Compensation

                  (a)      A&M will be compensated at a rate of $125,000 per
                           month for the services of the CRO.

                  (b)      A&M will receive fees based on the following hourly
                           rates for the services of the other Officers:

                                    Managing Directors          $475 - $675

                                    Directors                   $375 - $475

                                    Associates                  $275 - $375

                                    Analysts                    $175 - $250

                           Kevin Hausler will be billed as a Director at the
                           rate of $400 an hour.

                           Such rates shall be subject to adjustment annually
                           at such time as A&M adjusts its rates generally,
                           provided any rate adjustment will not be made prior
                           to November 1, 2005. A&M agrees to provide a monthly
                           budget in advance to the Company for the purposes of
                           cash planning.

                  (c)      In addition, A&M will be reimbursed for its
                           reasonable out-of-pocket expenses of the Officers
                           and Consultants incurred in connection with this
                           assignment, such as travel, lodging, duplicating,
                           computer research, messenger and telephone charges.
                           In addition, A&M shall be reimbursed for the
                           reasonable fees and expenses of its counsel incurred
                           in connection with the preparation, negotiation and
                           enforcement of this Agreement, such expenses not to
                           exceed $10,000 without prior approval of the
                           Company. All fees and expenses will be billed and
                           payable on a monthly basis or more often if mutually
                           agreed to in advance by the parties.

                  (d)      An incentive fee will be considered if it is
                           determined within 45 days of the date of this
                           agreement that the basis for such a fee exists and
                           payment of an incentive fee would be appropriate.

                  (e)      A&M will bill the Company on a monthly basis in
                           arrears including hours and rates by name or monthly
                           rates by name. The Company shall pay such invoice
                           within 10 business days.

         6.       Term

                  The engagement will commence as of the date hereof and may be
                  terminated by either party without cause by giving two weeks
                  written notice to the other party. In the event of any such
                  termination, any fees and expenses due to A&M shall be
                  remitted promptly (including fees and expenses that accrued
                  prior to but were invoiced subsequent to such termination).
                  If the Company terminates this engagement without Cause or if
                  A&M terminates this engagement for Good Reason, A&M shall
                  also be entitled to receive an incentive fee agreed upon
                  pursuant to Section 5(d) provided the criteria for payment of
                  such fee occur within 6 months of the termination. The
                  Company may immediately terminate A&M's services hereunder at
                  any time for Cause by giving written notice to A&M. Upon any
                  such termination, the Company shall be relieved of all of its
                  payment obligations under this Agreement, except for the
                  payment of fees and expenses through the effective date of
                  termination (including fees and expenses that accrued prior
                  to but were invoiced subsequent to such termination) and its
                  obligations under paragraph 8. For purposes of this
                  Agreement, "Cause" shall mean if A&M breaches any of its
                  material obligations hereunder and does not cure such breach
                  within two weeks of the Company having given written notice
                  of such breach to A&M describing in reasonable detail the
                  nature of the alleged breach. A&M shall be entitled to
                  immediately terminate its services hereunder for Good Reason.
                  For purposes of this Agreement, termination for "Good Reason"
                  shall mean either its resignation caused by a breach by the
                  Company of any of its material obligations under this
                  Agreement that is not cured within two weeks of A&M having
                  given written notice of such breach to the Company describing
                  in reasonable detail the nature of the alleged breach or a
                  filing of a petition under Chapter 11 of the United States
                  Bankruptcy Code in respect of the Company unless within 45
                  days thereafter (or, if sooner, prior to the date on which a
                  plan of reorganization is confirmed or the case is converted
                  to one under Chapter 7), the Company has obtained judicial
                  authorization to continue the engagement on the terms herein
                  pursuant to an order which has become a final, nonappealable
                  order

         7.       Relationship of the Parties

                  The parties intend that an independent contractor
                  relationship will be created by this engagement letter.
                  Neither A&M nor any of its personnel or subcontractors
                  (including the Officers) is to be considered an employee or
                  agent of the Company and the personnel and subcontractors of
                  A&M are not entitled to any of the benefits that the Company
                  provides for the Company employees. The Company acknowledges
                  that A&M's engagement shall not constitute an audit, review
                  or compilation, or any other type of financial statement
                  reporting engagement that is subject to the rules of the
                  AICPA, SEC or other state or national professional or
                  regulatory body.

         8.       No Third Party Beneficiary

                  The Company acknowledges that all advice (written or oral)
                  given by the Officers or Consultants to the Company in
                  connection with this engagement is intended solely for the
                  benefit and use of the Company (limited to its Board of
                  Directors, management, investment banking advisors and its
                  outside counsel) in considering the matters to which this
                  engagement relates. The Company agrees that no such advice
                  shall be used for any other purpose or reproduced,
                  disseminated, quoted or referred to at any time in any manner
                  or for any purpose other than accomplishing the tasks
                  referred to herein without A&M's prior approval (which shall
                  not be unreasonably withheld), except as required by law.

         9.       Conflicts

                  A&M is not currently aware of any relationship that would
                  create a conflict of interest with the Company or those
                  parties-in-interest of which you have made us aware, but we
                  note A&M has been retained by VarTec Telecom Inc. and A&M
                  employees hold officer positions with such company. A&M has
                  established confidentiality measures with respect to
                  information about both companies to which it may have access.
                  Because A&M is a consulting firm that serves clients on a
                  national basis in numerous cases, both in and out of court,
                  it is possible that A&M may have rendered services to or have
                  business associations with other entities or people which had
                  or have or may have relationships with the Company, including
                  creditors of the Company. In the event you accept the terms
                  of this engagement, A&M will not represent, and A&M has not
                  represented, the interests of any such entities or people in
                  connection with this matter.

         10.      Confidentiality / Non-Solicitation

                  A&M and the Officers (and any Consultants) shall keep as
                  confidential all non-public information received from the
                  Company in conjunction with this engagement, except: (i) as
                  requested by the Company or its legal counsel; or (ii) as
                  required by legal proceedings. All obligations as to
                  non-disclosure shall cease as to any part of such information
                  to the extent that such information is or becomes public
                  other than as a result of a breach of this provision. The
                  Company and A&M agree not to solicit, recruit or hire any
                  employees of the other effective from the date of this
                  Agreement and continuing for a period of one year subsequent
                  to the termination of this engagement. Should either extend
                  offers of employment to the other's employee and should such
                  an offer be accepted, A&M will be entitled to a fee based
                  upon such individual's hourly rates multiplied by an assumed
                  annual billing of 2,000 hours and the Company will be
                  entitled to a fee of employee's salary for one year. This fee
                  would be payable at the time of the individual's acceptance
                  of employment.

         11.      Indemnification

                  The attached indemnification agreement is incorporated herein
                  by reference and shall be executed upon the acceptance of
                  this Agreement. Termination of this engagement shall not
                  affect these indemnification provisions, which shall remain
                  in full force and effect.

         12.      Miscellaneous

                  This engagement letter (together with the attached indemnity
                  provisions): (a) shall be governed and construed in
                  accordance with the laws of the State of New York, regardless
                  of the laws that might otherwise govern under applicable
                  principles of conflict of laws thereof; (b) incorporates the
                  entire understanding of the parties with respect to the
                  subject matter hereof; and (c) may not be amended or modified
                  except in writing executed by both parties hereto. The
                  Company and A&M agree to waive trial by jury in any action,
                  proceeding or counterclaim brought by or on behalf of the
                  parties hereto with respect to any matter relating to or
                  arising out of the engagement or the performance or
                  non-performance of A&M hereunder. In the event the Company
                  files under Chapter 11, the Company and A&M agree that the
                  Bankruptcy Court shall have exclusive jurisdiction over any
                  and all matters arising under or in connection with this
                  engagement letter and the indemnity provisions and in
                  connection with the services rendered by the Officers and
                  Consultants of A&M hereunder.

                  If the foregoing is acceptable to you, kindly sign the
                  enclosed copy to acknowledge your agreement with its terms.


                                             Very truly yours,

                                             Alvarez & Marsal, LLC



                                             By: /s/ Stan Springel
                                                 -----------------------------
                                                 Stan Springel
                                                 Title: Managing Director


                  Accepted and agreed:

                  McLeodUSA, Inc.



                  By: /s/ Chris A. Davis
                      -------------------------------
                      Chris Davis, Chairman of the Board of Directors