Document:

<PAGE>

                                                                   EXHIBIT 10.55

                               EXCHANGE AGREEMENT

                                  dated as of

                               September 30, 2001

                                 by and between

                             McLeodUSA Incorporated

                                      and

              The Purchasers Listed on the Signature Pages Hereto
<PAGE>

                               EXCHANGE AGREEMENT

          EXCHANGE AGREEMENT (this "Agreement"), dated as of September 30, 2001,
                                    ---------
by and between McLeodUSA Incorporated, a Delaware corporation (the "Company"),
                                                                    -------
and the entities listed on the signature page hereto under the caption
"Purchasers" (each such entity, a "Purchaser" and collectively, the
                                   ---------
"Purchasers").
 ----------

                             W I T N E S S E T H :

          WHEREAS, pursuant to that certain Stock Purchase Agreement, dated as
of August 30, 1999, by and between the Company and the entities listed on the
signature page thereto, the Company sold to the Purchasers and the Purchasers
purchased from the Company (i) an aggregate of 275,000 shares of the Company's
Series B Preferred Stock, par value $.01 per share (the "Series B Preferred
                                                         ------------------
Stock") and (ii) an aggregate of 125,000 shares of the Company's Series C
-----
Preferred Stock, par value $.01 per share (the "Series C Preferred Stock" and,
                                                ------------------------
collectively with the Series B Preferred Stock, the "1999 Preferred Shares");
                                                     ---------------------

          WHEREAS, upon the terms and subject to the conditions set forth in
this Agreement, (i) the Company wishes to issue to the Purchasers (x) an
aggregate of 275,000 shares of the Company's Series D Preferred Stock, par value
$.01 per share (the "Series D Preferred Stock"), in exchange for all of the
                     ------------------------
outstanding shares of Series B Preferred Stock held by the Purchasers and (y) an
aggregate of 125,000 shares of the Company's Series E Preferred Stock, par value
$.01 per share (the "Series E Preferred Stock" and, collectively with the Series
                     ------------------------
D Preferred Stock, the "New Preferred Shares"), in exchange for all of the
                        --------------------
outstanding shares of the Series C Preferred Stock held by the Purchasers (each
of the foregoing exchanges, an "Exchange" and, collectively, the "Exchanges"),
                                --------                          ---------
and (ii) the Purchasers desire to consummate the Exchanges.

          WHEREAS, the Purchasers and the Company desire to provide for the
Exchanges and to establish certain rights and obligations in connection
therewith.

          NOW, THEREFORE, in consideration of the premises and the mutual
representations, warranties, covenants and agreements set forth in this
Agreement and in the Termination Agreement, the parties hereto agree as follows:

                                   ARTICLE I

                                   EXCHANGES

          1.1.  Exchanges.  Upon the terms and subject to the conditions set
                ---------
forth herein, at the Closing (as defined below), (a) the Company shall issue to
the Purchasers (i)
<PAGE>

an aggregate of 275,000 shares of Series D Preferred Stock and (ii) an aggregate
of 125,000 shares of Series E Preferred Stock, and (b) the Purchasers shall
surrender to the Company, in exchange therefor, all of the outstanding 1999
Preferred Shares held by the Purchasers. The number of shares of Series D
Preferred Stock and the number of shares of Series E Preferred Stock issued to
each Purchaser, and the 1999 Preferred Shares being surrendered in exchange
therefor by each Purchaser are set forth below such Purchaser's name on the
signature page hereto; provided, that the Purchasers shall have the right to
                       --------
reallocate among the Purchasers the New Preferred Shares to be issued to each
Purchaser by delivering written notice of such reallocation to the Company not
less than three days prior to the Closing so long as such reallocation does not
change the total number of New Preferred Shares being issued hereunder.

          1.2.  The Closing; Deliveries.  (a)  The closing of the Exchanges
                -----------------------
(the "Closing") shall take place at the offices of Fried, Frank, Harris, Shriver
      -------
& Jacobson, One New York Plaza, New York, New York 10004 at 9:00 a.m. on the
fifth business day following the satisfaction or waiver of the conditions set
forth in Article V (other than those conditions that by their nature are to be
satisfied at the Closing, but subject to the satisfaction or waiver of those
conditions) or at such other place, time and/or date as shall be mutually agreed
by the Company and the Purchasers (the date of the Closing, the "Closing Date").
                                                                 ------------

          (b) As promptly as practicable after the filing of the Certificates of
Designation with the Secretary of State of the State of Delaware, the Company
shall deliver to each Purchaser certificates representing the New Preferred
Shares, each registered in the name of such Purchaser in the respective amounts
set forth on the signature pages hereto or the reallocation notice referred to
in Section 1.1, as applicable. Delivery of such certificates shall be made
against receipt by the Company of the stock certificates representing the 1999
Preferred Shares.

          1.3.  Cancellation of the 1999 Preferred Shares.  The Company shall
                -----------------------------------------
take all actions necessary so that, upon receipt of the stock certificates
representing the 1999 Preferred Shares, the 1999 Preferred Shares shall be
retired and assume the status of authorized and unissued shares of the class of
preferred stock undesignated as to series.

          1.4.  Capitalized Terms.  Capitalized terms not otherwise defined
                -----------------
herein shall have the meanings ascribed to such terms in Section 8.1.

                                   ARTICLE II

                 REPRESENTATIONS AND WARRANTIES OF THE COMPANY

                                       2
<PAGE>

          The Company hereby represents and warrants to each Purchaser, as of
the date hereof and as of the Closing, as follows:

          2.1. Organization; Subsidiaries. (a) The Company is a corporation duly
               --------------------------
organized, validly existing and in good standing under the laws of the State of
Delaware and has the requisite corporate power and authority to carry on its
business as it is now being conducted. The Company is duly qualified and
licensed as a foreign corporation to do business, and is in good standing (and
has paid all relevant franchise or analogous taxes), in each jurisdiction where
the character of its assets owned or held under lease or the nature of its
business makes such qualification necessary, except where the failure to so
qualify or be licensed would not individually or in the aggregate have a
Material Adverse Effect.

          (b) Except as set forth on Schedule 2.1(b), (i) the Company owns,
either directly or indirectly through one or more Subsidiaries, all of the
capital stock or other equity interests of the Significant Subsidiaries free and
clear of all liens, charges, claims, security interests, restrictions, options,
proxies, voting trusts or other encumbrances ("Encumbrances") and (ii) there are
                                               ------------
no outstanding subscription rights, options, warrants, convertible or
exchangeable securities or other rights of any character whatsoever relating to
issued or unissued capital stock or other equity interests of any Significant
Subsidiary, or any Commitments of any character whatsoever relating to issued or
unissued capital stock or other equity interests of any Significant Subsidiary
or pursuant to which any Significant Subsidiary is or may become bound to issue
or grant additional shares of its capital stock or other equity interests or
related subscription rights, options, warrants, convertible or exchangeable
securities or other rights, or to grant preemptive rights.  Except for the
Subsidiaries and except as set forth on Schedule 2.1(b), the Company does not
own, directly or indirectly, any interest in any corporation, limited liability
company, partnership, business association or other Person in excess of 9.9% of
the outstanding equity.

          2.2.  Due Authorization.  The Company has all right, corporate power
                -----------------
and authority to enter into this Agreement and each of the other Transaction
Documents to which it is a party and to consummate the transactions contemplated
hereby and thereby. The execution and delivery by the Company of this Agreement
and each of the other Transaction Documents to which it is a party, the issuance
and delivery of the New Preferred Shares by the Company and the compliance by
the Company with each of the provisions of this Agreement and each of the other
Transaction Documents to which it is a party (including the reservation and
issuance of the Conversion Shares and the consummation by the Company of the
transactions contemplated hereby and thereby) (a) are within the corporate power
and authority of the Company, and (b) have been duly authorized by all necessary
corporate action of the Company. This Agreement has been, and each of the other
Transaction Documents to which the Company is a party when

                                       3
<PAGE>

executed and delivered by the Company will be, duly and validly executed and
delivered by the Company, and this Agreement constitutes, and each of such other
Transaction Documents when executed and delivered by the Company will
constitute, a valid and binding agreement of the Company enforceable against the
Company in accordance with its terms except as such enforcement is limited by
bankruptcy, insolvency and other similar laws affecting the enforcement of
creditors' rights generally and for limitations imposed by general principles of
equity. The Conversion Shares have been validly reserved for issuance, and upon
issuance, will be duly and validly issued and outstanding, fully paid, and
nonassessable. The terms, designations, powers, preferences and relative
participation, optional and other special rights, qualifications, limitations
and restrictions of the Series D Preferred Stock and the Series E Preferred
Stock will be as set forth in the Certificate of Designation for the Series D
Preferred Stock and the Certificate of Designation for the Series E Preferred
Stock (collectively, the "Certificates of Designation"), the forms of which are
                          ---------------------------
attached to this Agreement as Exhibits 2.2A and 2.2B. The New Preferred Shares
issued to the Purchasers in accordance with the terms of the Certificates of
Designation, when issued and delivered in accordance with the terms of this
Agreement, will be validly issued and outstanding, fully paid and non-
assessable, free and clear of any Encumbrances and not subject to the preemptive
or other similar rights of the stockholders of the Company.

          2.3.  Capitalization.  As of the date hereof, the authorized capital
                --------------
stock of the Company consists of (i) 2,000,000,000 shares of the Company's Class
A Common Stock, par value $.01 per share ("Class A Common Stock"), of which, as
                                           --------------------
of September 25, 2001, 626,950,228 shares were issued and outstanding and of
which no more than 1,000,000 additional shares (excluding any shares issued upon
exercise of outstanding options disclosed on Schedule 2.3) have been issued
between September 25, 2001 and the date hereof; (ii) 22,000,000 shares of Class
B Common Stock, par value $0.01 per share (the "Class B Common Stock" and,
                                                --------------------
together with the Class A Common Stock, the "Common Stock"), of which, as of the
                                             ------------
date hereof, no shares are issued and outstanding; (iii) 2,000,000 shares of
serial preferred stock, par value $0.01 per share, of which as of the date
hereof 1,149,375 shares are issued and outstanding as 6.75% Series A Cumulative
Convertible Preferred Stock (the "Series A Preferred Stock") and 400,000 are
                                  ------------------------
issued and outstanding as the 1999 Preferred Shares; and (iv) 10,000,000 shares
of Class II serial preferred stock, par value $.001 per share, of which, as of
the date hereof, no shares are issued and outstanding. All of the issued and
outstanding shares of Class A Common Stock, Series A Preferred Stock and the
1999 Preferred Shares have been duly authorized and are validly issued, fully
paid and nonassessable. Except as set forth on Schedule 2.3, no shares of
capital stock of the Company are entitled to preemptive rights. Except as set
forth on Schedule 2.3 or as otherwise contemplated by this Agreement, there are
no other outstanding subscription rights, options, warrants, convertible or
exchangeable securities or other rights of any character whatsoever relating to
issued or

                                       4
<PAGE>

unissued capital stock of the Company, or any Commitments of any character
whatsoever relating to issued or unissued capital stock of the Company or
pursuant to which the Company is or may become bound to issue or grant
additional shares of its capital stock or related subscription rights, options,
warrants, convertible or exchangeable securities or other rights, or to grant
preemptive rights.  Except as set forth on Schedule 2.3 or as otherwise
contemplated by this Agreement, (i) the Company has not agreed to register any
securities under the Securities Act or under any state securities law or granted
registration rights to any Person or entity and (ii) there are no voting trusts,
stockholders agreements, proxies or other Commitments or understandings in
effect to which the Company is a party or of which it has Knowledge with respect
to the voting or transfer of any of the outstanding shares of Class A Common
Stock, Series A Preferred Stock or 1999 Preferred Shares.  To the extent that
any options, warrants or any of the other rights described above are
outstanding, the issuance of the New Preferred Shares and any future issuance of
Conversion Shares will not result in an adjustment of the exercise or conversion
price or number of shares issuable upon the exercise or conversion of any such
options, warrants or other rights.

          2.4.  SEC Reports.  The Company has timely filed all proxy statements,
                -----------

reports and other documents required to be filed by it under the Exchange Act
and made available to the Purchasers complete copies of all annual reports,
quarterly reports, proxy statements and other reports filed by the Company under
the Exchange Act, each as filed with the SEC (collectively, the "SEC Reports").
                                                                 -----------
Each SEC Report was, on the date of its filing, in compliance in all material
respects with the requirements of its respective report form and the Exchange
Act and did not, on the date of its filing, contain any untrue statement of a
material fact or omit to state a material fact required to be stated therein or
necessary to make the statements therein, in the light of the circumstances
under which they were made, not misleading.

          2.5.  Financial Statements.  The consolidated financial statements
                --------------------
of the Company (including any related schedules and/or notes) included in the
SEC Reports have been prepared in accordance with United States generally
accepted accounting principles ("GAAP") consistently followed throughout the
                                 ----
periods involved (except as may be indicated in the notes thereto) and fairly
present in accordance with GAAP the consolidated financial condition, results of
operations, cash flows and changes in stockholders' equity of the Company and
the Subsidiaries as of the respective dates thereof and for the respective
periods then ended (except as may be indicated in the notes thereto and except,
in the case of interim statements, for the absence of footnotes and as permitted
by Form 10-Q and subject to changes resulting from year-end adjustments, none of
which are material in amount or effect). Except as set forth on Schedule 2.5 or
disclosed in the SEC Reports, neither the Company nor any Subsidiary has any
liability or obligation (whether accrued, absolute, contingent, unliquidated or
otherwise, whether

                                       5
<PAGE>

known or unknown, whether due or to become due and regardless of when asserted),
except (i) liabilities and obligations in the respective amounts reflected or
reserved against in the audited consolidated balance sheet of the Company and
the Subsidiaries as of December 31, 2000, (ii) liabilities and obligations
incurred in the ordinary course of business since December 31, 2000 or (iii)
liabilities and obligations which individually or in the aggregate would not
reasonably be expected to have or result in a Material Adverse Effect.

          2.6.  Absence of Certain Changes.  Except as set forth on Schedule
                --------------------------
2.6 or as disclosed in the SEC Reports, since December 31, 2000 neither the
Company nor any of the Subsidiaries has suffered any change, event or
development or series of changes, events or developments which individually or
in the aggregate has had or would reasonably be expected to have a Material
Adverse Effect or, to the Knowledge of the Company, an adverse effect on the
ability of the Company to perform its obligations under this Agreement or any of
the Transaction Documents to which it is a party.

          2.7.  Litigation.  (a)  Except as set forth on Schedule 2.7(a) or as
                ----------
disclosed in the SEC Reports, there is no claim, action, suit, investigation or
proceeding ("Litigation") pending or, to the Knowledge of the Company,
             ----------
threatened against the Company or any of the Subsidiaries or involving any of
their respective properties or assets by or before any court, arbitrator or
other Governmental Entity which (i) in any manner challenges or seeks to
prevent, enjoin, alter or materially delay the transactions contemplated by this
Agreement or (ii) if resolved adversely to the Company or a Subsidiary would
reasonably be expected to have a Material Adverse Effect.

          (b) Except as set forth on Schedule 2.7(b) or as disclosed in the SEC
Reports, neither the Company nor any of the Subsidiaries is in default under or
in breach of any order, judgment or decree of any court, arbitrator or other
Governmental Entity, except for defaults or breaches, which individually or in
the aggregate would not reasonably be expected to have a Material Adverse
Effect.

          2.8.  Consents, No Violations.  Except as set forth on Schedule 2.8,
                -----------------------
neither the execution, delivery or performance by the Company of this Agreement
or any of the other Transaction Documents to which it is a party nor the
consummation of the transactions contemplated hereby or thereby will (a)
conflict with, or result in a breach or a violation of, any provision of the
certificate of incorporation or by-laws or other organizational documents of the
Company or any of the Subsidiaries including, without limitation, any of the
provisions of the Certificate of Designation for the Series A Preferred Stock;
(b) constitute, with or without notice or the passage of time or both, a breach,
violation or default, create an Encumbrance, or give rise to any right of
termination, modification, cancellation, prepayment, suspension, limitation,
revocation or acceleration, under (i) any Law or (ii) any provision of any
agreement or other instrument

                                       6
<PAGE>

to which the Company or any of the Subsidiaries is a party or pursuant to which
any of them or any of their assets or properties is subject, except, with
respect to the matters set forth in this clause (ii), for breaches, violations,
defaults, Encumbrances, or rights of termination, modification, cancellation,
prepayment, suspension, limitation, revocation or acceleration, which,
individually or in the aggregate, would not reasonably be expected to result in
a Material Adverse Effect or, to the Knowledge of the Company, adversely affect
the ability of the Company to consummate the transactions contemplated by this
Agreement or any Transaction Document to which it is a party; or (c) except for
the filings of the Certificates of Designation with the Secretary of State of
the State of Delaware, any required filing under the HSR Act, the Exchange Act,
the Securities Act and other filings or notifications that are immaterial to the
consummation of the transactions contemplated hereby, require any consent,
approval or authorization of, notification to, filing with, or exemption or
waiver by, any Governmental Entity or any other Person on the part of the
Company or any of the Subsidiaries. Without limiting the generality of the
foregoing (i) no consent or other approval of the holders of the Series A
Preferred Stock is required in connection with the consummation of the
transactions contemplated hereby or the performance by the Company of any of its
obligations under this Agreement or any Transaction Document to which it is a
party, (ii) the issuance of the New Preferred Shares and any future issuance of
Conversion Shares will not result in any anti-dilution or other adjustment to
the conversion price or the number of shares of Class A Common Stock issuable
upon conversion of the Series A Preferred Stock or (iii) the holders of the
Series A Preferred Stock will not be entitled to exercise any voting rights as a
result of any of the provisions contained in this Agreement or any other
Transaction Documents.

          2.9.  Compliance with Laws. Except as set forth on Schedule 2.9 or as
                --------------------
disclosed in the SEC Reports, the Company and the Subsidiaries are in compliance
in all material respects with all Laws and the Company and the Subsidiaries
possess all material licenses, franchise permits, consents, registrations,
certificates, and other governmental or regulatory permits, authorizations or
approvals required for the operation of the business as presently conducted and
for the ownership, lease or operation of the Company's and its Subsidiaries'
properties (collectively, "Licenses").  Except as set forth on Schedule 2.9,
                           --------
the Company and the Subsidiaries have all Licenses, and all of such Licenses are
valid and in full force and effect, and the Company and the Subsidiaries have
duly performed and are in compliance in all material respects with all of their
obligations under such Licenses.

          2.10. Commitments.  Schedule 2.10 sets forth a complete and correct
                -----------
list of each contract, agreement, understanding, arrangement and commitment of
any nature whatsoever, whether written or oral, including all amendments thereof
and supplements thereto ("Commitments") of the following types to which the
                          -----------
Company or any Subsidiary

                                       7
<PAGE>

is a party or by or to which the Company or any Subsidiary or any of their
properties may be bound or subject, (i) Commitments, to the Knowledge of the
Company, containing covenants purporting to limit the freedom of the Company or
any Subsidiary to compete in any line of business in any geographic area or to
hire any individual or group of individuals, except in connection with or
resulting from acquisitions or potential acquisitions, (ii) Commitments relating
to capital expenditures in excess of $10,000,000, (iii) Commitments relating to
indentures, mortgages, promissory notes, loan agreements, guarantees, letters of
credit or other agreements or instruments of the Company or any Subsidiary
involving amounts in excess of $5,000,000, (iv) Commitments in respect of any
joint venture, partnership or other similar arrangement, (v) Commitments with
any Governmental Entity involving payments in excess of $5,000,000 and (vi)
Commitments relating to interconnection agreements with local carriers,
Commitments with resellers and material Commitments with customers in each case
involving payments in excess of $5,000,000 per year.

          2.11. Brokers or Finders.  Except for Goldman, Sachs & Co., whose
                ------------------
fees will be paid by the Company, upon the consummation of the transactions
contemplated by this Agreement, no agent, broker, investment banker or other
Person is or will be entitled to any broker's or finder's fee or any other
commission or similar fee from the Company or any of the Subsidiaries in
connection with any of the transactions contemplated by this Agreement or the
other Transaction Documents.

          2.12. Section 203 of the DGCL; Takeover Statute.  The Board of
                -----------------------------------------
Directors has taken all actions necessary or advisable so that the restrictions
contained in Section 203 of the DGCL applicable to a "business combination" (as
defined in such Section) will not apply to the execution, delivery or
performance of this Agreement or any of the other Transaction Documents or the
consummation of the transactions contemplated hereby or thereby. The execution,
delivery and performance of this Agreement or any of the other Transaction
Documents and the consummation of the transactions contemplated hereby or
thereby will not cause to be applicable to the Company any "fair price,"
"moratorium," "control share acquisition" or other similar antitakeover statute
or regulation enacted under state or federal laws.

          2.13. Offering of the New Preferred Shares. Neither the Company nor
                ------------------------------------
any Person acting on its behalf has taken or will take any action (including,
without limitation, any offering of any securities of the Company under
circumstances which would require, under the Securities Act, the integration of
such offering with the offering of the New Preferred Shares) which might
reasonably be expected to subject the offering or issuance of the New Preferred
Shares to the registration requirements of Section 5 of the Securities Act.

                                       8
<PAGE>

          2.14. Disclosure. Neither this Agreement nor any other Transaction
                ----------
Document, nor any schedule or exhibit hereto or thereto, nor any certificate
furnished to the Purchasers by or on behalf of the Company in connection with
the transactions contemplated hereby and thereby, contains any untrue statement
of a material fact or omits to state a material fact necessary in order to make
the statements contained herein or therein not misleading (for purposes of the
preceding sentence, any preliminary document or written information shall be
disregarded if a final or updated version of such document or written
information was delivered to the Purchasers by the Company prior to the date
hereof). To the Company's Knowledge the financial forecasts furnished by the
Company to the Purchasers have been reasonably prepared and reflect the best
currently available estimates and judgment of the Company's management as to the
expected future financial performance of the Company and the Subsidiaries. There
is no fact or information relating to the Company and/or any of its Subsidiaries
that, to the Company's Knowledge, would reasonably be expected to be material to
the Company and its Subsidiaries taken as a whole and that has not been
disclosed to the Purchasers.

                                  ARTICLE III

                REPRESENTATIONS AND WARRANTIES OF THE PURCHASERS

          Each Purchaser hereby represents and warrants to the Company,
severally and not jointly, as of the date hereof and as of the Closing, as
follows:

          3.1.  Acquisition for Investment.  Such Purchaser is acquiring the
                --------------------------
New Preferred Shares, for its own account, for investment and not with a view
to, or for sale in connection with, the distribution thereof within the meaning
of the Securities Act.

          3.2.  Restricted Securities.  Such Purchaser understands that
                ---------------------
(i) except as provided in the Registration Rights Agreement, the New Preferred
Shares and any Conversion Shares that may be issued will not be registered under
the Securities Act or any state securities laws by reason of their issuance by
the Company in a transaction exempt from the registration requirements thereof
and (ii) the New Preferred Shares and any Conversion Shares that may be issued
may not be sold unless such disposition is registered under the Securities Act
and applicable state securities laws or is exempt from registration thereunder.

          3.3.  No Brokers or Finders.  No agent, broker, investment banker
                ---------------------
or other Person is or will be entitled to any broker's or finder's fee or any
other commission or similar fee from the Purchasers in connection with the
transactions contemplated by this Agreement or the other Transaction Documents.

                                       9
<PAGE>

          3.4. Accredited Investor. Such Purchaser is an "accredited investor"
               -------------------
(as defined in Rule 501(a) under the Securities Act). Such Purchaser has
sufficient knowledge and experience in financial and business matters so as to
be capable of evaluating the merits and risks of its investment in the New
Preferred Shares and is capable of bearing the economic risks of such
investment.

          3.5  Organization. Such Purchaser is a limited partnership duly
               ------------
organized, validly existing and in good standing under the laws of the State of
Delaware and has the requisite power and authority to carry on its business as
it is now being conducted.

          3.6. Due Authorization. Such Purchaser has all right, power and
               -----------------
authority to enter into this Agreement and each of the other Transaction
Documents to which it is a party and to consummate the transactions contemplated
hereby and thereby. The execution and delivery by such Purchaser of this
Agreement and each of the other Transaction Documents to which it is a party and
the compliance by such Purchaser with each of the provisions of this Agreement
and each of the Transaction Documents to which it is a party (including the
consummation by such Purchaser of the transactions contemplated hereby and
thereby) (a) are within the power and authority of such Purchaser and (b) have
been duly authorized by all necessary action on the part of such Purchaser. This
Agreement has been, and each of the other Transaction Documents to which it is a
party when executed and delivered by such Purchaser will be, duly and validly
executed and delivered by such Purchaser, and this Agreement constitutes, and
each of such other Transaction Documents when executed and delivered by such
Purchaser will constitute, a valid and binding agreement of such Purchaser
enforceable against such Purchaser in accordance with its respective terms
except as such enforcement is limited by bankruptcy, insolvency and other
similar laws affecting the enforcement of creditors' rights generally and for
limitations imposed by general principles of equity.

          3.7. Consents, No Violations. Neither the execution, delivery or
               -----------------------
performance by such Purchaser of this Agreement or any of the other Transaction
Documents to which it is a party nor the consummation of the transactions
contemplated hereby or thereby will (a) conflict with, or result in a breach or
a violation of, any provision of the organizational documents of such Purchaser;
(b) constitute, with or without notice or the passage of time or both, a breach,
violation or default, create an Encumbrance, or give rise to any right of
termination, modification, cancellation, prepayment, suspension, limitation,
revocation or acceleration, under (i) any Law, or (ii) any provision of any
agreement or other instrument to which such Purchaser is a party or pursuant to
which the Purchaser or its assets or properties is subject, except, with respect
to the matters set forth in clause (ii), for breaches, violations, defaults,
Encumbrances, or rights of termination, modification, cancellation, prepayment,

                                       10
<PAGE>

suspension, limitation, revocation or acceleration, which, individually or in
the aggregate, would not materially adversely affect the ability of such
Purchaser to consummate the transactions contemplated by this Agreement or any
Transaction Document to which it is a party; or (c) except for any required
filing under the HSR Act and the filings set forth on Schedule 3.7, require any
consent, approval or authorization of, notification to, filing with, or
exemption or waiver by, any Governmental Entity or any other Person on the part
of the Purchaser.

          3.8.  Ownership of the 1999 Preferred Shares.  Such Purchaser is the
                --------------------------------------
lawful owner of the 1999 Preferred Shares set forth opposite such Purchaser's
name on the signature page hereto, which shares are to be delivered and sold to
the Company, and upon delivery and sale of, and payment for, such shares, as
provided for in this Agreement, such Purchaser will convey to the Company good
and marketable title to such shares, free and clear of all Encumbrances.

          3.9.  Litigation.  There is no Litigation pending or, to the knowledge
                ----------
of such Purchaser, threatened against such Purchaser or any of its Affiliates or
involving any of its properties or assets by or before any court, arbitrator or
other Governmental Entity which in any manner challenges or seeks to prevent,
enjoin, alter or materially delay the transactions contemplated by this
Agreement.

                                   ARTICLE IV

                                   COVENANTS

          4.1.  Conduct of Business by the Company Pending the Closing.  The
                ------------------------------------------------------
Company covenants and agrees that, during the period from the date of this
Agreement and continuing until the earlier of the termination of this Agreement
or the Closing, except for actions unanimously approved by the Company's Board
of Directors at a duly called and held meeting or unless the Purchasers
otherwise agree in writing, the Company shall, and shall cause each of the
Subsidiaries to, (i) conduct its business only in the ordinary course and
consistent with past practice; (ii) use reasonable best efforts to preserve and
maintain its assets and properties and its relationships with its customers,
suppliers, advertisers, distributors, agents, officers and employees and other
Persons with which it has significant business relationships; (iii) use
reasonable best efforts to maintain all of the material assets it owns or uses
in the ordinary course of business consistent with past practice; (iv) use
reasonable best efforts to preserve the goodwill and ongoing operations of its
business; (v) maintain its books and records in the usual, regular and ordinary
manner, on a basis consistent with past practice; and (vi) comply in all
material respects with applicable Laws. Except as expressly contemplated by this
Agreement or as set forth on Schedule 4.1, between the date of this Agreement
and the Closing, the

                                       11
<PAGE>

Company shall not, and shall cause each of the Subsidiaries not to, do any of
the following without the prior written consent of the Purchaser, which consent
shall not be unreasonably withheld or delayed:

          (a) (i) issue any debt securities, (ii) incur any additional
indebtedness (other than indebtedness pursuant to the Company's Senior Secured
Credit Facilities), (iii) assume, grant, guarantee or endorse, or make any other
accommodation or arrangement making the Company or any Subsidiary responsible
for, any liabilities or other obligations of any other Person or (iv) make any
loans, advances or capital contributions to, or investments in, any Person;

          (b) change any method of accounting or accounting practice used by the
Company or any Subsidiary, other than such changes required by GAAP;

          (c) repurchase, redeem (except pursuant to Section 4.5 of the
Company's Certificate of Incorporation) or otherwise acquire or exchange any
share of Common Stock or other equity interests; except for issuances of Class A
Common Stock pursuant to the exercise of options to purchase Class A Common
Stock outstanding on the date hereof and other issuances of Class A Common
Stock, in each case as listed on Schedule 2.3, issue or sell any additional
shares of the capital stock of, or other equity interests in, the Company or any
Subsidiary, or securities convertible into or exchangeable for such shares or
other equity interests, or issue or grant any subscription rights, options,
warrants or other rights of any character relating to shares of such capital
stock, such other equity interests or such securities; or declare, set aside,
make or pay any dividend, or make any distribution, in respect of any shares of
capital stock of the Company other than as required with respect to the Series A
Preferred Stock;

          (d) amend the Company's or any Subsidiary's charter or by-laws or
other organizational documents except with respect to the filing of the
Certificates of Designation;

          (e) take any action that is reasonably likely to result in (i) any of
the representations and warranties set forth in Article II becoming false or
inaccurate in any material respect as of the Closing Date or (ii) any of the
conditions to the obligations of the Purchasers set forth in Section 5.2 not
being satisfied; or

          (f) agree to take any of the actions restricted by this Section 4.1.

                                       12
<PAGE>

          4.2. Press Releases; Interim Public Filings. The Company shall, and
               --------------------------------------
shall cause each Subsidiary to, deliver to the Purchasers complete and correct
copies of all press releases and public filings made between the date hereof and
the Closing Date, and, to the extent any such press releases and public filings
refer in any way to the Purchasers and/or their Affiliates, shall give the
Purchasers the reasonable opportunity to review and comment on such releases and
filings, in each case prior to release in the form in which it will be issued.

          4.3. HSR Act. Each of the Purchasers and the Company shall cooperate
               -------
in making filings under the HSR Act and shall use its reasonable best efforts to
take, or cause to be taken, all actions necessary, proper or advisable to
consummate and make effective as promptly as practicable the transactions
contemplated by this Agreement, including using its reasonable best efforts to
resolve such objections, if any, as the Antitrust Division of the Department of
Justice or the Federal Trade Commission or state antitrust enforcement or other
Governmental Entities may assert under antitrust Laws with respect to the
transactions contemplated hereby.

          4.4. Consents; Approvals. The Company shall use its reasonable best
               -------------------
efforts to obtain all consents, waivers, exemptions, approvals, authorizations
or orders (collectively, "Consents") (including, without limitation (i) Consents
                          --------
required to avoid any breach, violation, default, encumbrance or right of
termination, modification, cancellation, prepayment, suspension, limitation,
revocation or acceleration of any material agreement or instrument to which the
Company is a party or its properties or assets are bound, (ii) all Consents
pursuant to the Company's or any Subsidiary's financing documents, including
without limitation, all indentures and credit agreements of the Company or any
Subsidiary, and (iii) all United States and foreign governmental and regulatory
rulings and approvals). The Company also shall use its reasonable best efforts
to obtain all necessary state securities laws or blue sky permits and approvals
required to carry out the transactions contemplated hereby and shall furnish all
information as may be reasonably requested in connection with any such action.

          4.5. Listing. The Company shall use its reasonable best efforts to
               -------
continue to have its Class A Common Stock listed on the NASDAQ National Market
System (the "NMS") or a national securities exchange for so long as any New
             ---
Preferred Shares or any shares of Class A Common Stock are outstanding. Prior to
the Closing, the Company shall prepare and submit to the NMS a listing
application covering the Conversion Shares and shall obtain approval for the
listing of such shares, subject to, in the case of the Conversion Shares,
official notice of issuance.

          4.6. Board Representation; Observers, VCOC. (a) Section 8(b)(i) of the
               -------------------------------------
Certificate of Designation for the Series D Preferred Stock provides that the
holders of Series D Preferred Stock shall be entitled to elect two directors to
the Board of Directors

                                       13
<PAGE>

subject to the terms set forth therein. In addition, Section 8(b)(i) of the
Certificate of Designation for the Series E Preferred Stock provides that the
holders of Series E Preferred Stock shall be entitled to designate one non-
voting observer to attend and participate in (but not vote at) all meetings of
the Board of Directors (the "Series E Non-Voting Observer"). Accordingly,
                             ----------------------------
subject to the Certificate of Designation for the Series D Preferred Stock, the
Purchasers set forth on Schedule 4.6(a)(1), as holders of Series D Preferred
Stock, shall be entitled to designate for election to the Board of Directors two
directors (the "Purchasers' Directors") and subject to the Certificate of
                ---------------------
Designation for the Series E Preferred Stock, the Purchasers set forth on
Schedule 4.6(a)(2), as holders of Series E Preferred Stock, shall be entitled to
designate the one Series E Non-Voting Observer, in each case as set forth on the
applicable schedule. Theodore J. Forstmann and Erskine B. Bowles, each of whom
currently serves on the Board of Directors as a director designee of the Series
B Preferred Stock, shall serve as the initial Purchasers' Directors for purposes
of the Series D Preferred Stock, and Thomas H. Lister, who currently serves as
the non-voting observer for the Series C Preferred Stock, shall serve as the
initial Series E Non-Voting Observer. Thereafter, in connection with any annual
meeting of stockholders at which the term of a Purchasers' Director is to
expire, the Company will take all necessary action to cause a Purchasers'
Director to be nominated and use its reasonable best efforts to cause such
Purchasers' Director to be elected to the Board of Directors. In the event a
vacancy shall exist in the office of a Purchasers' Director, the Purchasers
shall be entitled to designate a successor and the Board of Directors shall
elect such successor and, in connection with the meeting of stockholders of the
Company next following such election, nominate such successor for election as
director by the stockholders and use its reasonable best efforts to cause the
successor to be elected. The Series E Non-Voting Observer shall have the same
access to information concerning the business and operations of the Company and
its Subsidiaries and at the same time as directors of the Company, and shall be
entitled to participate in discussions and consult with the Board of Directors
without voting. Without limiting the generality of the foregoing, the
Purchasers' Directors and the Series E Non-Voting Observer may inspect all
contracts, books, records, personnel, offices and other facilities and
properties of the Company and, to the extent available to the Company after the
Company uses reasonable efforts to obtain them, the accountants' work papers,
and the Purchasers' Directors and the Series E Non-Voting Observer may make such
copies and inspections thereof as the Purchasers' Directors and the Series E
Non-Voting Observer may request. The Company shall furnish the Purchasers'
Directors and the Series E Non-Voting Observer with such financial and operating
data and other information with respect to the business and properties of the
Company as the Purchasers' Directors and the Series E Non-Voting Observer may
request. The Company shall permit each of the Purchasers' Directors and the
Series E Non-Voting Observer to discuss the affairs, finances and accounts of
the Company with, and to make proposals and furnish advice with respect thereto,
the principal officers of the Company. The provision of any such information to

                                       14
<PAGE>

the Series E Non-Voting Observer shall be subject to the receipt by the Company
of a confidentiality agreement covering such information and reasonably
acceptable to the Company and the Series E Non-Voting Observer. Notwithstanding
anything contained in this Section 4.6 to the contrary, the provisions of the
Certificates of Designation shall govern the rights of holders of New Preferred
Shares to elect directors (including any Purchasers' Directors).

          (b) The rights set forth in Section 4.6(a) are intended to satisfy the
requirement of contractual management rights for purposes of qualifying each of
the Purchaser's ownership interests in the Company as venture capital
investments for purposes of the Department of Labor's "plan assets" regulations,
and in the event such rights are not satisfactory for such purpose as to any
such Purchaser, the Company and such Purchaser shall reasonably cooperate in
good faith to agree upon mutually satisfactory management rights which satisfy
such regulations.

          (c) The Company shall promptly reimburse the Purchasers' Directors and
the Series E Non-Voting Observer for all reasonable expenses incurred by them in
connection with their attendance at meetings and any other activities undertaken
in their capacity as directors or an observer consistent with the policies of
the Company in effect on the date hereof or as such policies may be modified and
generally applied to the Company's Board of Directors.

          4.7. Certificates of Designation. The Company shall, as promptly as
               ---------------------------
practicable, and in any case no later than 10:00 a.m., on October 1, 2001, cause
the Certificates of Designation to be filed with the Secretary of State of the
State of Delaware.

          4.8. Cooperation. Each of the Purchasers and the Company agrees to use
               -----------
its reasonable best efforts to take, or cause to be taken, all such further
actions as shall be necessary to make effective and consummate the transactions
contemplated by this Agreement.

          4.9. Access to Property; Records. Between the date hereof and the
               ---------------------------
Closing the Company shall afford the Purchasers and their employees, counsel,
accountants, partners, investors, and other authorized representatives
reasonable access upon notice, during normal business hours, to the assets,
properties, offices and other facilities, Commitments and books and records of
the Company and of the Subsidiaries, and to the outside auditors of the Company
and their work papers relating to the Company and the Subsidiaries. The parties
hereto agree that no investigation by the Purchasers or their representatives
shall affect or limit the scope of the representations and warranties of the
Company contained in this Agreement or in any other Transaction Document

                                       15
<PAGE>

delivered pursuant hereto or limit the liability for breach of any such
representation or warranty.

          4.10. Reserve Shares. The Company will at all times reserve and keep
                --------------
available, solely for issuance and delivery upon conversion of the New Preferred
Shares, the number of shares of Class A Common Stock from time to time issuable
upon conversion of all shares of the New Preferred Shares at the time
outstanding. All shares of Class A Common Stock issuable upon conversion of the
New Preferred Shares shall be duly authorized and, when issued upon such
conversion or exercise, shall be validly issued, fully paid and nonassessable.

          4.11. [INTENTIONALLY OMITTED]

          4.12  Restrictions on Transfer. The Purchasers will not, prior to the
                ------------------------
earlier of (a) September 15, 2004 or (b) the occurrence of a Termination Event
(as defined below), sell, transfer, assign, convey, gift, mortgage, pledge,
encumber, hypothecate, or otherwise dispose of, directly or indirectly,
("Transfer") any of the New Preferred Shares or the Conversion Shares except for
  --------
(i) Transfers between and among the Purchasers and their Affiliates provided
such Transfer is done in accordance with the transfer restrictions applicable to
the New Preferred Shares or the Conversion Shares under federal and state
securities laws and the Affiliate transferee agrees to be bound by the
restrictions applicable to such New Preferred Shares or Conversion Shares,
including without limitation the agreements set forth in this Section 4.12, and
(ii) Transfers (w) required to comply with applicable Law provided that the
general partners of the Purchasers shall not be the party that institutes any
proceeding out of which such Transfer is required by Law, (x) pursuant to a bona
fide tender or exchange offer made pursuant to a merger or other agreement
approved by the Board of Directors to acquire securities of the Company;
provided, that the Purchasers may not tender or exchange in such offer unless at
--------  ----
least 50% of the outstanding securities of the Company have previously been
tendered or exchanged by other holders of the Company's securities in connection
therewith, (y) following any stock merger or other stock business combination
transaction to which the Company is a party if Clark and Mary McLeod sell any of
the securities beneficially owned and received by them in such transaction
following such transaction and then only in an amount equal to the product of
(A) the percentage that the securities beneficially owned and sold by Clark and
Mary McLeod represents of the total number of securities beneficially owned by
Clark and Mary McLeod and (B) the total number of securities beneficially owned
by such Purchasers (determined in all cases on an as converted basis) and (z)
pursuant to any cash merger, or other business combination transaction to which
the Company is a party or involved in which the Class A Common Stock of the
Company's stockholders is exchanged for cash upon consummation of such merger or
other business combination. Notwithstanding any other provision of this Section
4.12, no Purchaser shall avoid the provisions of this Section 4.12 by making one
or more Transfers

                                       16
<PAGE>

to one or more Affiliates and then disposing of all or any portion of such
Purchaser's interest in any such Affiliate. For purposes of this Section 4.12, a
"Termination Event" shall occur if at any time the position of Chief Executive
 -----------------
Officer of the Company (or any higher position within the Company) is not
occupied by either Clark McLeod or Stephen Gray. Each Purchaser agrees that it
may not exercise any conversion rights with respect to the New Preferred Shares
until September 15, 2004; provided that nothing contained herein shall be deemed
                          -------- ----
to prevent the Purchasers from exercising their conversion rights with respect
to the New Preferred Shares at any time after September 15, 2004 or at any time
prior thereto in connection with a Termination Event or in connection with a
Transfer permitted pursuant to Section 4.12(b)(ii). Nothing contained herein
shall be deemed to limit the ability of the limited partners in the Purchasers
from transferring, directly or indirectly, their limited partnership interests
in the Purchasers or the general partners of the Purchasers from transferring,
directly or indirectly, up to 15% of the equity interests in the Purchasers at
any time or from time to time.

          4.13 Standstill Agreement. (a) During the period commencing on the
               --------------------
date hereof and ending on the earlier of (i) September 15, 2009 (the "Standstill
                                                                      ----------
Period") or (ii) the date these provisions terminate as provided herein, except
------
as (x) specifically permitted by this Agreement or (y) specifically approved in
writing in advance by the Board of Directors of the Company, the Purchasers
shall not, and shall cause any Affiliates controlled by them to not, in any
manner, directly or indirectly:

          (i) acquire, or offer or agree to acquire, or become the beneficial
     owner of or obtain any rights in respect of any capital stock of the
     Company, except, for any shares of Class A Common Stock that may be
     issuable upon the conversion of the New Preferred Shares or otherwise as
     permitted pursuant to this Agreement, provided, that the foregoing
                                           --------
     limitation shall not prohibit the acquisition of securities of the Company
     or any of its successors issued as dividends or as a result of stock splits
     and similar reclassifications or received in a merger or other business
     combination involving the New Preferred Shares or shares of Class A Common
     Stock (including any Conversion Shares) held by the Purchasers or any of
     their Affiliates at the time of such dividend, split or reclassification or
     merger or business combination;

          (ii) solicit proxies or consents or become a "participant" in a
     "solicitation" (as such terms are defined or used in Regulation 14A under
     the Exchange Act) of proxies or consents with respect to any voting
     securities of the Company or any of its successors or initiate or become a
     participant in any stockholder proposal or "election contest" (as such term
     is defined or used in Rule 14a-11 under the Exchange Act) with respect to
     the Company or any of its successors or induce others to initiate the same,
     or otherwise seek to advise or influence any person with respect to the
     voting of any voting securities of the Company or any of its successors
     (except

                                       17
<PAGE>

     for activities undertaken by the Purchasers or the Purchasers' Directors in
     connection with solicitations by the Board of Directors);

          (iii)  publicly or privately propose, encourage, solicit or
     participate in the solicitation of any person or entity to acquire, offer
     to acquire or agree to acquire, by merger, tender offer, purchase or
     otherwise, the Company or a substantial portion of its assets or more than
     5% of the outstanding capital stock (except in connection with the
     registration of securities pursuant to the Registration Rights Agreement);
     and

          (iv) directly or indirectly join in or in any way participate in a
     pooling agreement, syndicate, voting trust or other arrangement with
     respect to the Company's voting securities or otherwise act in concert with
     any other Person (other than Affiliates), for the purpose of acquiring,
     holding, voting or disposing of the Company's securities.

          (b) Nothing contained in this Section 4.13 shall be deemed to restrict
the manner in which the Purchasers' Directors or the Series E Non-Voting
Observer participate in deliberations or discussions of the Board of Directors.

          (c) The standstill provisions set forth herein shall terminate on the
earliest of (i) the last day of the Standstill Period, (ii) the date that the
position of Chief Executive Officer of the Company (or any higher position
within the Company) is not occupied by either Clark McLeod or Stephen Gray,
(iii) upon any breach by the Company in any material respect of any covenant or
agreement contained in this Agreement or in any Transaction Document, (iv) upon
the filing of a voluntary bankruptcy petition by the Company or on the 60th day
following the filing of an involuntary bankruptcy petition against the Company
if such petition is not discharged with prejudice during such 60-day period or
(v) upon the occurrence of a change in control of the Company if the Purchasers
are permitted to effect a Transfer in accordance with the provisions of Section
4.12(b)(ii)(x), (y) and (z) hereof.

                                   ARTICLE V

                                   CONDITIONS

          5.1. Conditions to Obligations of the Purchasers and the Company. The
               -----------------------------------------------------------
respective obligations of the Purchasers and the Company to consummate the
transactions contemplated hereby are subject to the satisfaction or waiver at or
prior to the Closing of each of the following conditions:

                                       18
<PAGE>

          (a) No statute, rule or regulation or order of any court or
administrative agency shall be in effect which prohibits the consummation of the
transactions contemplated hereby;

          (b) Any waiting period (and any extension thereof) under the HSR Act
applicable to this Agreement and the transactions contemplated hereby shall have
expired or been terminated; and

          (c) Any material required filings or other consents, if any, of state
regulatory bodies shall have been made or obtained.

          5.2. Conditions to Obligations of the Purchasers. The obligations of
               -------------------------------------------
the Purchasers to consummate the transactions contemplated hereby shall be
subject to the satisfaction or waiver at or prior to the Closing of each of the
following conditions:

          (a) Each of the representations and warranties of the Company
contained in this Agreement shall be true and correct when made and as of the
Closing (except to the extent such representations and warranties are made as of
a particular date, in which case such representations and warranties shall have
been true and correct in all material respects as of such date), except for
failures to be true and correct which individually or in the aggregate would not
reasonably be expected to have a Material Adverse Effect;

          (b) The Company shall have performed, satisfied and complied in all
material respects with all of its covenants and agreements set forth in this
Agreement to be performed, satisfied and complied with prior to or at the
Closing;

          (c) The Company shall have delivered to the Purchasers an officer's
certificate certifying as to the Company's compliance with the conditions set
forth in clauses (a) and (b) of this Section 5.2;

          (d) The Company shall have executed and delivered a Registration
Rights Agreement in the form of Exhibit 5.2(d) hereto (the "Registration Rights
                                                            -------------------
Agreement"), and the Registration Rights Agreement shall be in full force and
---------
effect;

          (e) The Company shall have executed and delivered a Termination
Agreement in the form of Exhibit 5.2(e) hereto (the "Termination Agreement"),
                                                     ---------------------
and the Termination Agreement shall be in full force and effect;

          (f) The Certificates of Designation shall have been duly filed with
the Secretary of State of the State of Delaware in accordance with the laws of
the State of Delaware and the Certificates of Designation shall be in full force
and effect;

                                       19
<PAGE>

          (g) The Conversion Shares shall have been duly authorized and reserved
for issuance and such Conversion Shares shall have been approved for listing on
the NMS, subject to official notice of issuance;

          (h) The Purchasers shall have received an opinion from (i) the General
Counsel of the Company, with respect to good standing, non-contravention and the
capitalization of the Company and (ii) Hogan & Hartson L.L.P., outside counsel
to the Company, with respect to the due incorporation, due authorization,
validity of the New Preferred Shares, Securities Act of 1933 exemption and the
valid and binding nature of this Agreement, the Termination Agreement and the
Registration Rights Agreement, in the form of Exhibit 5.2(h)(i) and Exhibit
5.2(h)(ii), respectively;

          (i) The Purchasers shall have received an opinion from Willkie Farr &
Gallagher, outside counsel to the Company, in the form of Exhibit 5.2(i) hereto;

          (j) There shall not have occurred any event, circumstances, condition,
fact, effect or other matter which has had or would reasonably be expected to
have a material adverse effect (x) on the business, assets, financial condition,
prospects, or results of operations of the Company and its Subsidiaries taken as
a whole or (y) on the ability of the Company and such Subsidiaries to perform
any material obligation under this Agreement or to consummate the transactions
contemplated hereby.

          5.3. Conditions to Obligations of the Company. The obligations of the
               ----------------------------------------
Company to consummate the transactions contemplated hereby shall be subject to
the satisfaction or waiver at or prior to the Closing of each of the following
conditions:

          (a) Each of the representations and warranties of the Purchasers
contained in this Agreement shall be true and correct when made and as of the
Closing (except to the extent such representations and warranties are made as of
a particular date, in which case such representations and warranties shall have
been true and correct in all material respects as of such date), except for
failures to be true and correct which individually or in the aggregate would not
reasonably be expected to have a material adverse effect on the Purchasers'
ability to perform its obligations under this Agreement;

          (b) The Purchasers shall have performed, satisfied and complied in all
material respects with all of their covenants and agreements set forth in this
Agreement to be performed, satisfied and complied with prior to or at the
Closing Date;

          (c) The Purchasers shall have delivered to the Company an officer's
certificate certifying as to the Purchasers' compliance with the conditions set
forth in clauses (a) and (b) of this Section 5.3;

                                       20
<PAGE>

          (d) The Company shall have received an opinion from Fried, Frank,
Harris, Shriver & Jacobson, outside counsel to the Purchasers, with respect to
non-contravention, due formation, due authorization, and the valid and binding
nature of this Agreement, the Termination Agreement and the Registration Rights
Agreement in the form of Exhibit 5.3(d) hereto; and

          (e) The Purchasers shall have executed and delivered the Termination
Agreement, and the Termination Agreement shall be in full force and effect.

                                   ARTICLE VI

                                  TERMINATION

          6.1. Termination. This Agreement may be terminated at any time prior
               -----------
to the Closing:

          (a) by mutual written agreement of the Company and the Purchasers; or

          (b) by either the Purchasers or the Company if the Closing shall not
have been consummated on or before October 31, 2001 (provided that the right to
terminate this Agreement under this Section 6.1(b) shall not be available to any
party whose failure to fulfill any obligation under this Agreement has been the
cause of or resulted in the failure of the Closing to occur on or before such
date); or

          (c) by either the Purchasers or the Company if a court of competent
jurisdiction or governmental, regulatory or administrative agency or commission
shall have issued a nonappealable final order, decree or ruling or taken any
other action having the effect of permanently restraining, enjoining or
otherwise prohibiting the transactions contemplated by this Agreement.

          6.2. Effect of Termination. In the event of the termination of this
               ---------------------
Agreement pursuant to Section 6.1, this Agreement shall forthwith become void
and there shall be no liability on the part of any party hereto (or any
stockholder, director, officer, partner, employee, agent, consultant or
representative of such party) except as set forth in this Section 6.2, provided
that nothing contained in this Agreement shall relieve any party from liability
for any breach of this Agreement and provided further that this Section 6.2 and
Sections 8.2 (other than the second sentence thereof), 8.3, 8.13, 8.14 and 8.15
shall survive termination of this Agreement.

                                       21
<PAGE>

                                  ARTICLE VII

                                INDEMNIFICATION

          7.1. Survival. The representations and warranties of the parties
               --------
hereto contained in this Agreement or in any of the other Transaction Documents
shall expire on the 18-month anniversary of the Closing Date, except that the
representations and warranties set forth in Sections 2.1(a), 2.2, 2.3, 3.5 and
3.6 shall survive until the expiration of the applicable statute of limitations
(including any extensions thereof). After the expiration of such periods, any
claim by a party hereto based upon any such representation or warranty shall be
of no further force and effect, except to the extent a party has asserted a
claim in accordance with this Article VII for breach of any such representation
or warranty prior to the expiration of such period, in which event any
representation or warranty to which such claim relates shall survive with
respect to such claim until such claim is resolved as provided in this Article
VII. The covenants and agreements of the parties hereto contained in this
Agreement or in any of the other Transaction Documents shall survive the Closing
until performed in accordance with their terms.

          7.2. Indemnification. (a) The Company shall indemnify, defend and hold
               ---------------
harmless the Purchasers, their Affiliates, and their respective officers,
directors, partners, members, employees, agents, representatives, successors and
assigns (each a "Purchasers Indemnified Person") from and against all Losses
                 -----------------------------
incurred or suffered by a Purchaser Indemnified Person arising from (i) the
breach of any of the representations or warranties made by the Company in this
Agreement or any other Transaction Document or (ii) the breach of any covenant
or agreement made by the Company in this Agreement or any other Transaction
Document. Notwithstanding the foregoing, (A) no claim may be made against the
Company for indemnification pursuant to Section 7.2(a)(i) unless the aggregate
liability of the Company exceeds $10 million, and the Company shall then only be
liable for Losses in excess of such amount and (B) the Company's maximum
liability for indemnification pursuant to Section 7.2(a)(i) shall not exceed
$250,000,000.

          (b) The Purchasers shall indemnify, defend and hold harmless the
Company, its Affiliates, and their respective officers, directors, partners,
members, employees, agents, representatives, successors and assigns (each a
"Company Indemnified Person") from and against all Losses incurred or suffered
 --------------------------
by a Company Indemnified Person arising from (i) the breach of any of the
representations or warranties made by the Purchasers in this Agreement or any
other Transaction Document or (ii) the breach of any covenant or agreement made
by the Purchasers in this Agreement or any other Transaction Document.
Notwithstanding the foregoing, (A) no claim may be made against the Purchasers
for indemnification pursuant to Section 7.2(b)(i) unless the

                                       22
<PAGE>

aggregate liability of the Purchasers exceeds $10 million, and the Purchasers
shall then only be liable for Losses in excess of such amount and (B) the
Purchasers' maximum liability for indemnification pursuant to Section 7.2(b)(i)
shall not exceed $250,000,000.

          (c) A party seeking indemnification under this Section 7.2 shall,
promptly upon becoming aware of the facts indicating that a claim for
indemnification may be warranted, give to the party from whom indemnification is
being sought a notice of claim relating to such Loss (a "Claim Notice").  Each
                                                         ------------
Claim Notice shall specify the nature of the claim, the applicable provision(s)
of this Agreement or other instrument under which the claim for indemnity
arises, and, if possible, the amount or the estimated amount thereof.  No
failure or delay in giving a Claim Notice (so long as the same is given prior to
expiration of the representation or warranty upon which the claim is based) and
no failure to include any specific information relating to the claim (such as
the amount or estimated amount thereof) or any reference to any provision of
this Agreement or other instrument under which the claim arises shall affect the
obligation of the party from whom indemnification is sought.

          7.3. Inspections; No Other Representations. The Purchasers are
               -------------------------------------
informed and sophisticated purchasers, and have undertaken such investigation
and have been provided with and have evaluated such documents and information as
they deem necessary to enable them to make an informed decision with respect to
the execution, delivery and performance of this Agreement. Each Purchaser will
undertake prior to the Closing such further investigation and request such
additional documents and information as it deems necessary. Each Purchaser
agrees to accept the New Preferred Shares based upon its own inspection,
examination and determination with respect thereto as to all matters, and
without reliance upon any express or implied representations or warranties of
any nature made by or on behalf of or imputed to the Company, except as
expressly set forth in this Agreement. Without limiting the generality of the
foregoing, each Purchaser acknowledges that the Company makes no representation
or warranty with respect to any projections, estimates or budgets delivered to
or made available to Purchasers of future revenues, future results of operations
(or any component thereof), future cash flows or future financial condition (or
any component thereof) of the Company and its Subsidiaries or the future
business and operations of the Company and the Subsidiaries except as expressly
set forth in this Agreement.

          7.4. Exclusivity. Except as specifically set forth in this Agreement
               -----------
and except in the case of fraud, effective as of the Closing, each party hereby
waives any rights and claims such party may have against the other party hereto,
whether in law or in equity, relating to any breach of any representation or
warranty by any party hereunder. After the Closing, Sections 7.1, 7.2(a) and
7.2(b) will provide the exclusive remedy for any misrepresentation or breach of
warranty, except in the case of fraud.

                                       23
<PAGE>

                                  ARTICLE VIII

                                 MISCELLANEOUS

          8.1. Defined Terms; Interpretations. The following terms, as used
               ------------------------------
herein, shall have the following meanings:

          "Affiliate" shall have the meaning ascribed to such term in Rule 12b-2
           ---------
of the General Rules and Regulations under the Exchange Act.

          "Agreement" shall have the meaning ascribed thereto in the preamble.
           ---------

          "Board of Directors" shall mean the Board of Directors of the Company.
           ------------------

          "Certificates of Designation" shall have the meaning ascribed thereto
           ---------------------------
in Section 2.2.

          "Claim Notice" shall have the meaning ascribed thereto in Section
           ------------
7.2(c).

          "Class A Common Stock" shall have the meaning ascribed thereto in
           --------------------
Section 2.3, which meaning shall include any and all securities of any kind
whatsoever of the Company which may be exchanged for or converted into such
Class A Common Stock, and any and all securities of any kind whatsoever of the
Company which may be issued on or after the date hereof in respect of, in
exchange for, or upon conversion of shares of Class A Common Stock pursuant to a
merger, consolidation, stock split, stock dividend, recapitalization of the
Company or otherwise.

          "Closing" shall have the meaning ascribed thereto in Section 1.2(a).
           -------

          "Closing Date" shall have the meaning ascribed thereto in Section
           ------------
1.2(a).

          "Commitments" shall have the meaning ascribed thereto in Section 2.10.
           -----------

          "Common Stock" shall have the meaning ascribed thereto in Section 2.3.
           ------------

          "Company" shall have the meaning ascribed thereto in the preamble.
           -------

          "Company Indemnified Person" shall have the meaning ascribed thereto
           --------------------------
in Section 7.2(b).

          "Consents" shall have the meaning ascribed thereto in Section 4.4.
           --------

          "Conversion Shares" shall mean any shares of Class A Common Stock
           -----------------
issued upon conversion of any New Preferred Shares, any and all securities of
any kind

                                       24
<PAGE>

whatsoever of the Company which may be exchanged for or converted into such
Class A Common Stock, and any and all securities of any kind whatsoever of the
Company which may be issued on or after the date hereof in respect of, in
exchange for, or upon conversion of shares of Class A Common Stock pursuant to a
merger, consolidation, stock split, stock dividend, recapitalization of the
Company or otherwise.

          "DGCL" shall mean the Delaware General Corporation Law.
           ----

          "Encumbrances" shall have the meaning ascribed thereto in Section
           ------------
2.1(b).

          "Exchange" shall have the meaning ascribed thereto in the recitals.
           --------

          "Exchange Act" shall mean the Securities Exchange Act of 1934, as
           ------------
amended, or any successor federal statute, and the rules and regulations of the
SEC thereunder, all as the same shall be in effect at the time.  Reference to a
particular section of the Securities Exchange Act of 1934, as amended, shall
include reference to the comparable section, if any, of any such successor
federal statute.

          "GAAP" shall have the meaning ascribed thereto in Section 2.5.
           ----

          "Governmental Entity" shall mean any supernational, national, foreign,
           -------------------
federal, state or local judicial, legislative, executive, administrative or
regulatory body or authority.

          "HSR Act" shall mean the Hart-Scott-Rodino Antitrust Improvements Act
           -------
of 1976, as amended, and the rules and regulations thereunder.

          "Knowledge", with respect to the Company, shall mean the knowledge of
           ---------
Clark McLeod, Stephen Gray, Blake O. Fisher, Jr. and Randall Rings.

          "Laws" shall include all foreign, federal, state, and local laws,
           ----
statutes, ordinances, rules, regulations, orders, judgments, decrees and bodies
of law.

          "Licenses" shall have the meaning ascribed thereto in Section 2.9.
           --------

          "Litigation" shall have the meaning ascribed thereto in Section
           ----------
2.7(a).

          "Losses" shall mean each and all of the following items:  claims,
           ------
losses, liabilities, obligations, payments, damages (actual or punitive),
charges, judgments, fines, penalties, amounts paid in settlement, costs and
expenses (including, without limitation, interest which may be imposed in
connection therewith, costs and expenses of investigation, actions, suits,
proceedings, demands, assessments and fees, expenses and disbursements of
counsel, consultants and other experts).

                                       25
<PAGE>

          "Material Adverse Effect" shall mean a material adverse effect on the
           -----------------------
properties, business, prospects, operations, results of operations, earnings,
assets, liabilities or condition (financial or otherwise) of the Company and its
Subsidiaries taken as a whole.

          "New Preferred Shares" shall have the meaning ascribed thereto in the
           --------------------
recitals.

          "Person" shall mean any individual, firm, corporation, limited
           ------
liability company, partnership, company or other entity, and shall include any
successor (by merger or otherwise) of such entity.

          "Purchasers" shall have the meaning ascribed thereto in the preamble.
           ----------

          "Purchasers Indemnified Person" shall have the meaning ascribed
           -----------------------------
thereto in Section 7.2(a).

          "Registration Rights Agreement" shall have the meaning ascribed
           -----------------------------
thereto in Section 5.2(d).

          "SEC" shall mean the Securities and Exchange Commission.
           ---

          "SEC Reports" shall have the meaning ascribed thereto in Section 2.4.
           -----------

          "Securities Act" shall mean the Securities Act of 1933, as amended, or
           --------------
any successor federal statute, and the rules and regulations of the SEC
thereunder, all as the same shall be in effect at the time.  Reference to a
particular section of the Securities Act shall include reference to the
comparable section, if any, of such successor federal statute.

          "Senior Secured Credit Facilities" shall mean the Company's $1.3
           --------------------------------
billion of senior secured credit facilities that were entered into on May 31,
2000 with a syndicate of financial institutions, as currently in effect.

          "Series A Preferred Stock" shall have the meaning ascribed thereto in
           ------------------------
Section 2.3.

          "Series B Preferred Stock"  shall have the meaning ascribed thereto in
           ------------------------
the recitals.

          "Series C Preferred Stock" shall have the meaning ascribed thereto in
           ------------------------
the recitals.

                                       26
<PAGE>

          "Series D Preferred Stock" shall have the meaning ascribed thereto in
           ------------------------
the recitals.

          "Series E Preferred Stock" shall have the meaning ascribed thereto in
           ------------------------
the recitals.

          "Significant Subsidiaries" shall mean the entities listed on Schedule
           ------------------------
8.1.

          "Subsidiary" shall mean as to the Company, each corporation,
           ----------
partnership or other entity of which shares of capital stock or other equity
interests having ordinary voting power (other than capital stock or other equity
interests having such power only by reason of the happening of a contingency) to
elect a majority of the board of directors or other managers of such
corporation, partnership or other entity are at the time owned, directly or
indirectly, or the management of which is otherwise controlled, directly or
indirectly, or both, by the Company.

          "Termination Agreement" shall have the meaning ascribed thereto in
           ---------------------
Section 5.2(e).

          "Transaction Documents" shall mean this Agreement, the Termination
           ---------------------
Agreement, the Certificates of Designation, the Registration Rights Agreement
and all other contracts, agreements, schedules, certificates and other documents
being delivered pursuant to or in connection with this Agreement or such other
documents or the transactions contemplated hereby or thereby.

          8.2. Fees and Expenses. All costs and expenses incurred in connection
               -----------------
with this Agreement shall be paid by the party incurring such costs or expense.

          8.3. Public Announcement. The Purchasers and the Company have
               -------------------
consulted with each other and issued a press release with respect to this
Agreement and the transactions contemplated hereby and neither shall issue any
further press release or make any further public statement without the prior
consent of the other, which consent shall not be unreasonably withheld or
delayed; provided, however, that a party may, without the prior consent of the
         -----------------
other party, issue such press release or make such public statement as may upon
the advice of counsel be required by Law, the NMS or any exchange on which the
Company's securities are listed and, to the extent time permits, it has used all
reasonable efforts to consult with the other party prior thereto.

                                       27
<PAGE>

          8.4. Restrictive Legends. In addition to the restrictions set forth in
               -------------------
Section 4.12, no New Preferred Shares may be transferred without registration
under the Securities Act and applicable state securities laws unless counsel to
the Company shall advise the Company that such transfer may be effected without
such registration. Each certificate representing any of the foregoing shall bear
legends in substantially the following form:

          THE COMPANY IS AUTHORIZED TO ISSUE MORE THAN ONE CLASS OR SERIES OF
          STOCK.  AS REQUIRED UNDER DELAWARE LAW, THE COMPANY SHALL FURNISH TO
          ANY HOLDER UPON REQUEST AND WITHOUT CHARGE, A FULL SUMMARY STATEMENT
          OF THE DESIGNATIONS, VOTING RIGHTS, PREFERENCES, LIMITATIONS AND
          SPECIAL RIGHTS OF THE SHARES OF EACH CLASS OR SERIES AUTHORIZED TO BE
          ISSUED BY THE COMPANY SO FAR AS THEY HAVE BEEN FIXED AND DETERMINED
          AND THE AUTHORITY OF THE BOARD OF DIRECTORS TO FIX AND DETERMINE THE
          DESIGNATIONS, VOTING RIGHTS, PREFERENCES, LIMITATIONS AND SPECIAL
          RIGHTS OF THE CLASSES AND SERIES OF SECURITIES OF THE COMPANY.

          THE SHARES REPRESENTED BY THIS CERTIFICATE HAVE NOT BEEN REGISTERED
          UNDER THE SECURITIES ACT OF 1933, AS AMENDED (THE "1933 ACT"), OR
          UNDER ANY APPLICABLE STATE LAWS.  THE SHARES REPRESENTED BY THIS
          CERTIFICATE HAVE BEEN ACQUIRED BY THE REGISTERED OWNER HEREOF FOR
          INVESTMENT AND NOT WITH A VIEW TO OR FOR SALE IN CONNECTION WITH ANY
          DISTRIBUTION THEREOF WITHIN THE MEANING OF THE 1933 ACT.  THE SHARES
          MAY NOT BE SOLD, PLEDGED, TRANSFERRED OR ASSIGNED EXCEPT IN A
          TRANSACTION WHICH IS EXEMPT UNDER THE PROVISIONS OF THE 1933 ACT OR
          ANY APPLICABLE STATE SECURITIES LAWS, OR PURSUANT TO AN EFFECTIVE
          REGISTRATION STATEMENT OR IN A TRANSACTION OTHERWISE

                                       28
<PAGE>

          IN COMPLIANCE WITH APPLICABLE FEDERAL AND STATE SECURITIES LAWS.

          THE SALE, PLEDGE, TRANSFER, ASSIGNMENT OR OTHER DISPOSITION OF THE
          SHARES REPRESENTED BY THIS CERTIFICATE IS RESTRICTED BY AND SUBJECT TO
          THE PROVISIONS OF AN EXCHANGE AGREEMENT DATED AS OF SEPTEMBER 30,
          2001, A COPY OF WHICH IS AVAILABLE UPON REQUEST FOR INSPECTION AT THE
          OFFICES OF THE COMPANY.  ANY SUCH REQUEST SHOULD BE ADDRESSED TO THE
          SECRETARY OF THE COMPANY.

In addition, each certificate representing New Preferred Shares shall bear a
legend in substantially the following form:

          THE SECURITIES EVIDENCED BY THIS CERTIFICATE SHALL BE REDEEMABLE AS
          PROVIDED IN THE CERTIFICATE OF DESIGNATION AND THE COMPANY'S AMENDED
          AND RESTATED CERTIFICATE OF INCORPORATION.  THE SECURITIES EVIDENCED
          BY THIS CERTIFICATE SHALL BE CONVERTIBLE INTO THE COMPANY'S CLASS A
          COMMON STOCK IN THE MANNER AND ACCORDING TO THE TERMS SET FORTH IN THE
          CERTIFICATE OF DESIGNATION.

and each certificate representing Conversion Shares shall bear a legend in
substantially the following form:

          THE SECURITIES EVIDENCED BY THIS CERTIFICATE SHALL BE REDEEMABLE AS
          PROVIDED IN THE COMPANY'S AMENDED AND RESTATED CERTIFICATE OF
          INCORPORATION.

          8.5. Further Assurances. At any time or from time to time after the
               ------------------
Closing, the Company, on the one hand, and the Purchasers, on the other hand,
agree to cooperate with each other, and at the request of the other party, to
execute and deliver any further instruments or documents and to take all such
further action as the other party may reasonably request in order to evidence or
effectuate the consummation of the

                                       29
<PAGE>

transactions contemplated hereby or by the other Transaction Documents and to
otherwise carry out the intent of the parties hereunder or thereunder.

          8.6. Successors and Assigns. This Agreement shall bind and inure to
               ----------------------
the benefit of the Company and the Purchasers and the respective successors,
permitted assigns, heirs and personal representatives of the Company and the
Purchasers, provided that prior to the Closing the Company may not assign its
            -------- ----
rights or obligations under this Agreement to any Person without the prior
written consent of the Purchasers, and provided further that the Purchasers may
                                       ---------------------
not assign their rights or obligations under this Agreement to any Person (other
than an Affiliate) without the prior written consent of the Company. In
addition, and whether or not any express assignment has been made, the
provisions of this Agreement which are for the Purchasers' benefit as purchasers
or holders of New Preferred Shares or Conversion Shares are also for the benefit
of, and enforceable by, any Affiliates of the Purchasers who hold such New
Preferred Shares or Conversion Shares and received such New Preferred Shares or
Conversion Shares in accordance with the terms of this Agreement.

          8.7. Entire Agreement. This Agreement and the other Transaction
               ----------------
Documents contain the entire agreement between the parties with respect to the
subject matter hereof and supersede all prior and contemporaneous arrangements
or understandings with respect thereto.

          8.8. Notices. All notices, requests, consents and other communications
               -------
hereunder to any party shall be deemed to be sufficient if contained in a
written instrument delivered in person or sent by telecopy, nationally
recognized overnight courier or first class registered or certified mail, return
receipt requested, postage prepaid, addressed to such party at the address set
forth below or such other address as may hereafter be designated in writing by
such party to the other parties:

               (i)  if to the Company, to:

                    McLeodUSA Incorporated
                    McLeodUSA Technology Park
                    6400 C Street SW
                    PO Box 3177
                    Cedar Rapids, Iowa  52406-3177
                    Telecopy No.: (319) 790-7901
                    Attention: Randall Rings, Esq.
                               Group Vice President and Chief Legal Officer

                    with a copy to (which shall not constitute notice):

                                       30
<PAGE>

                    Hogan & Hartson L.L.P.
                    Columbia Square
                    555 Thirteenth Street, N.W.
                    Washington, D.C.  20004
                    Telecopy No.:  (202) 637-5910
                    Attention:  Joseph G. Connolly, Jr., Esq.

               (ii) if to the Purchasers, to:

                    c/o Forstmann Little & Co.
                    767 Fifth Avenue
                    New York, NY  10153
                    Telecopy No.:  (212) 759-9059
                    Attention:  Thomas H. Lister

                    with a copy to:

                    Fried, Frank, Harris, Shriver & Jacobson
                    One New York Plaza
                    New York, NY  10004
                    Telecopy No.:  (212) 859-8587
                    Attention:  Robert C. Schwenkel, Esq.

          All such notices, requests, consents and other communications shall be
deemed to have been given or made if and when delivered personally or by
overnight courier to the parties at the above addresses or sent by electronic
transmission, with confirmation received, to the telecopy numbers specified
above (or at such other address or telecopy number for a party as shall be
specified by like notice).

          8.9. Amendments. The terms and provisions of this Agreement may be
               ----------
modified or amended, or any of the provisions hereof waived, temporarily or
permanently, in a writing executed and delivered by the Company and the
Purchasers. No waiver of any of the provisions of this Agreement shall be deemed
to or shall constitute a waiver of any other provision hereof (whether or not
similar). No delay on the part of any party in exercising any right, power or
privilege hereunder shall operate as a waiver thereof.

          8.10. Counterparts. This Agreement may be executed in any number of
                ------------
counterparts, and each such counterpart hereof shall be deemed to be an original
instrument, but all such counterparts together shall constitute but one
agreement.

                                       31
<PAGE>

          8.11. Headings. The headings of the sections of this Agreement have
                --------
been inserted for convenience of reference only and shall not be deemed to be a
part of this Agreement.

          8.12. Nouns and Pronouns. Whenever the context may require, any
                ------------------
pronouns used herein shall include the corresponding masculine, feminine or
neuter forms, and the singular form of names and pronouns shall include the
plural and vice versa.

          8.13. GOVERNING LAW. THIS AGREEMENT SHALL BE GOVERNED BY AND CONSTRUED
                -------------
IN ACCORDANCE WITH THE LAWS OF THE STATE OF NEW YORK WITHOUT GIVING EFFECT TO
THE PRINCIPLES OF CONFLICTS OF LAW.

          8.14. Submission to Jurisdiction. Each of the parties hereto 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, for any Litigation arising out of
or relating to this Agreement or the other Transaction Documents and the
transactions contemplated hereby and thereby (and agrees not to commence any
Litigation relating hereto or thereto except in such courts), and further agrees
that service of any process, summons, notice or document by U.S. registered mail
to its respective address set forth in this Agreement shall be effective service
of process for any Litigation brought against it in any such court. Each of the
parties hereto hereby irrevocably and unconditionally waives any objection to
the laying of venue of any Litigation arising out of this Agreement or the
transactions contemplated hereby in the courts of the State of New York or the
United States of America, in each case located in the County of New York, and
hereby further irrevocably and unconditionally waives and agrees not to plead or
claim in any such court that any such Litigation brought in any such court has
been brought in an inconvenient forum.

          8.15. WAIVER OF JURY TRIAL. THE COMPANY AND THE PURCHASERS HEREBY
                --------------------
WAIVE ANY RIGHT THEY MAY HAVE TO A TRIAL BY JURY IN RESPECT OF ANY ACTION,
PROCEEDING OR LITIGATION DIRECTLY OR INDIRECTLY ARISING OUT OF, UNDER OR IN
CONNECTION WITH THIS AGREEMENT OR THE TRANSACTION DOCUMENTS.

          8.16. Severability. Whenever possible, each provision of this
                ------------
Agreement shall be interpreted in such manner as to be effective and valid, but
if any provision of this Agreement is held to be invalid or unenforceable in any
respect, such invalidity or unenforceability shall not render invalid or
unenforceable any other provision of this Agreement.

                                       32
<PAGE>

                                    *  *  *

                                       33
<PAGE>

          IN WITNESS WHEREOF, the parties hereto have duly executed and
delivered this Agreement as of the date first above written.

PURCHASERS

FORSTMANN LITTLE & CO. EQUITY PARTNERSHIP-V, L.P.

By: FLC XXX Partnership, L.P.
    its general partner

    By:
       --------------------------------------
       Winston W. Hutchins,
       a general partner

<TABLE>
<CAPTION>
       Securities to be Surrendered                       New Securities to be Issued
No. of Series B         No. of Series C            No. of Series D           No. of Series E
Preferred  Shares       Preferred Shares           Preferred Shares          Preferred Shares
-----------------       ----------------           ----------------          ----------------
<S>                     <C>                        <C>                       <C>
        0                    125,000                       0                      125,000
</TABLE>

FORSTMANN LITTLE & CO. SUBORDINATED DEBT AND EQUITY MANAGEMENT BUYOUT
PARTNERSHIP-VI, L.P.

By: FLC XXIX Partnership, L.P.
    its general partner

    By:
       --------------------------------------
       Winston W. Hutchins,
       a general partner

<TABLE>
<CAPTION>
       Securities to be Surrendered                       New Securities to be Issued
No. of Series B         No. of Series C            No. of Series D           No. of Series E
Preferred  Shares       Preferred Shares           Preferred Shares          Preferred Shares
-----------------       ----------------           ----------------          ----------------
<S>                     <C>                        <C>                       <C>
   85,752.78                   0                      85,752.78                      0

</TABLE>

                                       34
<PAGE>

FORSTMANN LITTLE & CO. SUBORDINATED DEBT AND EQUITY
MANAGEMENT BUYOUT PARTNERSHIP-VII, L.P.

By: FLC XXXIII Partnership, L.P.
    its general partner

    By:
       -------------------------------------
       Winston W. Hutchins,
       a general partner

<TABLE>
<CAPTION>
       Securities to be Surrendered                       New Securities to be Issued
No. of Series B         No. of Series C            No. of Series D           No. of Series E
Preferred  Shares       Preferred Shares           Preferred Shares          Preferred Shares
-----------------       ----------------           ----------------          ----------------
<S>                     <C>                        <C>                       <C>
   189,247.22                  0                      189,247.22                     0
</TABLE>

McLEODUSA INCORPORATED

By:
   --------------------------------------
   Name:  Stephen C. Gray
   Title: President and Chief Executive Officer

                                       35<PAGE>

                                                                   EXHIBIT 10.56

                             TERMINATION AGREEMENT

          THIS TERMINATION AGREEMENT (this "Termination Agreement") is entered
into as of September 30, 2001, by and between McLeodUSA Incorporated, a Delaware
corporation (the "Company"), and the entities listed on the signature page
hereto under the caption "Purchasers" (each such entity, a "Purchaser" and
collectively, the "Purchasers").  Capitalized terms used herein which are
defined in the Exchange Agreement shall have the meanings set forth in the
Exchange Agreement, unless otherwise defined herein.

          WHEREAS, the Company and the Purchasers (the Company and the
Purchasers, collectively, the "Parties" and, individually, a "Party") entered
into a Stock Purchase Agreement, dated as of August 30, 1999, as amended (the
"1999 Stock Purchase Agreement"), pursuant to which the Company sold to the
Purchasers and the Purchasers purchased from the Company (i) an aggregate of
275,000 shares of the Company's Series B Preferred Stock, par value $.01 per
share, and (ii) an aggregate of 125,000 shares of the Company's Series C
Preferred Stock, par value $.01 per share;

          WHEREAS, the Parties have agreed to enter into an Exchange Agreement,
dated as of September 30, 2001 (the "Exchange Agreement"), and, upon the terms
and subject to the conditions set forth in the Exchange Agreement,

          (i)  the Company wishes to issue to the Purchasers (x) an aggregate of
               275,000 shares of the Company's Series D Preferred Stock, par
               value $.01 per share, in exchange for all of the outstanding
               shares of the Company's Series B Preferred Stock, par value $.01
               per share, held by the Purchasers and (y) an aggregate of 125,000
               shares of the Company's Series E Preferred Stock, par value $.01
               per share, in exchange for all of the outstanding shares of the
               Company's Series C Preferred Stock, par value $.01 per share,
               held by the Purchasers, and

         (ii)  the Purchasers wish to consummate the foregoing exchanges; and

          WHEREAS, in connection with entering into the Exchange Agreement, the
Parties wish to terminate the 1999 Stock Purchase Agreement and have agreed to
enter into this Termination Agreement.

          NOW, THEREFORE, in consideration of the foregoing and of the mutual
covenants and agreements hereinafter set forth, and for other good and
<PAGE>

valuable consideration, the receipt of which is hereby acknowledged, the
parties hereto hereby agree as follows:

1.   TERMINATION

          The 1999 Stock Purchase Agreement shall be terminated in its entirety
upon consummation of the transaction contemplated by the Exchange Agreement
(including, without limitation, the due filing of the Certificates of
Designation with the Secretary of State of the State of Delaware in accordance
with the laws of the State of Delaware and the delivery of certificates in
accordance with Section 1.2(b) of the Exchange Agreement), and shall thereafter
be of no further force and effect.  The Parties agree and confirm that there are
no unsatisfied obligations of any of the Parties under the 1999 Stock Purchase
Agreement except as provided for in Section 2.

2.   REMAINING OBLIGATIONS OF THE PARTIES

     2.1. Obligations pursuant to the 1999 Stock Purchase Agreement

          It is understood by the Parties that Sections 6.2, 8.2 (other than the
second sentence therein), 8.3, 8.13, 8.14 and 8.15 of the 1999 Stock Purchase
Agreement shall survive the termination of the 1999 Stock Purchase Agreement.

     2.2. Obligations regarding the Exchange Agreement

          It is understood by the Parties that concurrently with the execution
of this Termination Agreement the Parties will cause the execution of the
Exchange Agreement.

3.   MUTUAL RELEASE AND INDEMNITY

          Upon consummation of the transactions contemplated by the Exchange
Agreement, each of the Parties hereby shall release and forever discharge the
other Parties, and their heirs, successors and assigns, from any and all claims,
obligations or liabilities, whether now or hereafter existing, relating to the
1999 Stock Purchase Agreement except as provided for in Section 2, and shall
agree to indemnify and hold harmless the other Parties from any claim or
assertion of obligations or liabilities made by or on behalf of such releasing
and indemnifying Party.

                                       2
<PAGE>

4.   MISCELLANEOUS

     4.1. Binding Effect

          This Termination Agreement shall be binding upon and inure to the
benefit of the Parties hereto and their respective successors and permitted
assigns.

     4.2. Governing Law

          THIS TERMINATION AGREEMENT SHALL BE GOVERNED BY AND CONSTRUED IN
ACCORDANCE WITH THE LAWS OF THE STATE OF NEW YORK WITHOUT GIVING EFFECT TO THE
PRINCIPLES OF CONFLICTS OF LAW.

     4.3. Submission to Jurisdiction

          Each of the Parties hereto 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, for any litigation arising out of or relating to this Termination
Agreement and the transactions contemplated hereby and thereby (and agrees not
to commence any litigation relating hereto or thereto except in such courts),
and further agrees that service of any process, summons, notice or document by
U.S. registered mail to its respective address set forth in this Termination
Agreement shall be effective service of process for any litigation brought
against it in any such court.  Each of the Parties hereto hereby irrevocably and
unconditionally waives any objection to the laying of venue of any litigation
arising out of this Termination Agreement or the transactions contemplated
hereby in the courts of the State of New York or the United States of America,
in each case located in the County of New York, hereby further irrevocably and
unconditionally waives and agrees not to plead or claim in any such court that
any such litigation brought in any such court has been brought in an
inconvenient forum.

     4.4. Waiver of Jury Trial

          THE COMPANY AND THE PURCHASERS HEREBY WAIVE ANY RIGHT THEY MAY HAVE TO
A TRIAL BY JURY IN RESPECT OF ANY ACTION, PROCEEDING OR LITIGATION DIRECTLY OR
INDIRECTLY ARISING OUT OF, UNDER OR IN CONNECTION WITH THIS TERMINATION
AGREEMENT.

                                       3
<PAGE>

     4.5. Notices

          All notices, requests, consents and other communications hereunder to
any Party shall be deemed to be sufficient if contained in a written instrument
delivered in person or sent by telecopy, nationally recognized overnight courier
or first class registered or certified mail, return receipt requested, postage
prepaid, addressed to such Party at the address set forth below or such other
address as may hereafter be designated in writing by such Party to the other
Parties:

          (i)  if to the Company, to:

               McLeodUSA Incorporated
               McLeodUSA Technology Park
               6400 C Street SW
               PO Box 3177
               Cedar Rapids, Iowa  52406-3177
               Telecopy No.:  (319) 790-7901
               Attention:  Randall Rings, Esq.
                           Group Vice President and Chief Legal Officer

               with a copy to (which shall not constitute notice):

               Hogan & Hartson L.L.P.
               Columbia Square
               555 Thirteenth Street, N.W.
               Washington, D.C.  20004
               Telecopy No.:  (202) 637-5910
               Attention:  Joseph G. Connolly, Jr., Esq.

          (ii) if to the Purchasers, to:

               c/o Forstmann Little & Co.
               767 Fifth Avenue
               New York, NY  10153
               Telecopy No.:  (212) 759-9059
               Attention:  Thomas Lister

               with a copy to:

               Fried, Frank, Harris, Shriver & Jacobson
               One New York Plaza
               New York, NY  10004
               Telecopy No.:  (212) 859-8587
               Attention:  Robert C. Schwenkel, Esq.

                                       4
<PAGE>

All such notices, requests, consents and other communications shall be deemed to
have been given or made if and when delivered personally or by overnight courier
to the parties at the above addresses or sent by electronic transmission, with
confirmation received, to the telecopy numbers specified above (or at such other
address or telecopy number for a party as shall be specified by like notice).

     4.6. Execution

          This Termination Agreement may be executed in any number of
counterparts, and each such counterpart hereof shall be deemed to be an original
instrument, but all such counterparts together shall constitute but one
agreement.

                                   *    *  *

          IN WITNESS WHEREOF, the parties hereto have duly executed and
delivered this Termination Agreement as of the date first above written.

PURCHASERS

FORSTMANN LITTLE & CO. EQUITY PARTNERSHIP-V, L.P.

By:  FLC XXX Partnership, L.P.
     its general partner

     By:
         -------------------------
         Winston W. Hutchins,
         a general partner

FORSTMANN LITTLE & CO. SUBORDINATED DEBT AND EQUITY MANAGEMENT BUYOUT
PARTNERSHIP-VI, L.P.

By:  FLC XXIX Partnership, L.P.
     its general partner

     By:
         -------------------------
         Winston W. Hutchins,
         a general partner

                                       5
<PAGE>

FORSTMANN LITTLE & CO. SUBORDINATED DEBT AND EQUITY MANAGEMENT BUYOUT
PARTNERSHIP-VII, L.P.

By:  FLC XXXIII Partnership, L.P.
     its general partner

     By:
         -------------------------
         Winston W. Hutchins,
         a general partner

McLEODUSA INCORPORATED

By:
   --------------------------------
   Name:  Stephen C. Gray
   Title: President and Chief Executive Officer

                                       6

Source: [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00031-of-00352.parquet"}, [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00031-of-00352.parquet"}]]