AMENDMENT NO. 2

EXHIBIT 10.6

AMENDMENT NO. 2

TO SECOND AMENDED AND RESTATED CREDIT AGREEMENT

THIS AMENDMENT NO. 2 TO SECOND AMENDED AND RESTATED CREDIT AGREEMENT (this “Amendment”), dated as of March     , 2004, is made among CBeyond Communications, LLC, a Delaware limited liability company (“Borrower”), CBeyond Communications, Inc., a Delaware corporation (“Holdings”), Cbeyond Leasing, LP, a Delaware limited partnership (“Additional Borrower”) and Cisco Systems Capital Corporation, a Nevada corporation (“Lender” or “Agent”).

WHEREAS, Borrower, Holdings, Additional Borrower, Agent and the several financial institutions from time to time party thereto entered into a Second Amended and Restated Credit Agreement dated as of November 1, 2002 (as amended by Amendment No. 1 to Second Amended and Restated Credit Agreement dated as of June 30, 2003, the “Credit Agreement”);

WHEREAS, the parties have agreed to amend certain provisions of the Credit Agreement;

NOW, THEREFORE, in consideration of the premises, the mutual covenants herein contained, and other good and valuable consideration, the receipt of which is hereby acknowledged, the parties hereto agree as follows:

SECTION 1 Definitions; Interpretation.

(a) Terms Defined in Credit Agreement. All capitalized terms used in this Amendment (including in the recitals hereof) and not otherwise defined herein shall have the meanings assigned to them in the Credit Agreement.

(b) Interpretation. The rules of interpretation set forth in Section 1.2 of the Credit Agreement shall be applicable to this Amendment and are incorporated herein by this reference.

SECTION 2 Amendments to the Credit Agreement.

(a) Section 5.1(o)(i)(Leverage Ratio) of the Credit Agreement is hereby deleted in its entirety and the following text inserted in lieu thereof:

Leverage Ratio. On a consolidated basis, Borrower and its Subsidiaries shall not, as of the last day of any fiscal quarter, permit its ratio of Consolidated Funded Debt to EBITDA (measured on a rolling four quarter basis for the four fiscal quarters ended on the last day of each quarterly period set forth below) to be greater than the ratios indicated below:

(b) Section 5.1(o)(ii)(Minimum Total Revenues) of the Credit Agreement is hereby deleted in its entirety and the following text inserted in lieu thereof:

Minimum Total Revenues. On a consolidated basis, Borrower and its Subsidiaries shall maintain total revenues of Borrower and its Subsidiaries for each quarterly period set forth below of not less than the correlative amount indicated:

2

(c) Section 5.1(o)(iii)(Minimum EBITDA) of the Credit Agreement is hereby deleted in its entirety and the following text inserted in lieu thereof:

Minimum EBITDA. On a consolidated basis, Borrower and its Subsidiaries shall maintain EBITDA for each period of four fiscal quarters ended on a date set forth below of not less than the correlative amount indicated (bracketed amounts (< >) are negative):

3

(d) Section 5.1(o)(iv)(Interest Coverage Ratio) of the Credit Agreement is hereby deleted in its entirety and the following text inserted in lieu thereof:

Interest Coverage Ratio. On a consolidated basis, Borrower and its Subsidiaries shall not permit the ratio of EBITDA to Interest Expense for any period of four quarters ended on a date set forth below to be less than the ratio set forth below opposite such date:

(e) Section 5.1(o)(vi)(Minimum Customers) is hereby deleted in its entirety and the following text inserted in lieu thereof:

Minimum Customers. The number of revenue generating customers of Borrower and its Subsidiaries as of any date listed below shall not be less than the number listed opposite such date:

4

(f) Section 5.1(o)(vii)(Minimum Cash Reserves) of the Credit Agreement is hereby deleted in its entirety and the following text inserted in lieu thereof:

Minimum Cash Reserves. On a consolidated basis, Borrower and its Subsidiaries shall maintain at all times Minimum Cash Reserves of not less than $13,750,000.00.

(g) Section 5.01(o) of the Credit Agreement is hereby amended by adding the following text to the last paragraph thereof:

In the event that Borrower expands its business plan beyond the current four-market plan, Agent and the Lenders agree that they will consider in good faith amending the financial covenants set forth in this Section 5.01(o) in connection with the expansion of Borrower’s business.

(h) The last paragraph of Section 5.1(o) is hereby amended by deleting the definition of “Minimum Cash Reserves” appearing therein and inserting the following definition in lieu thereof:

“Minimum Cash Reserves” means, with respect to Borrower and its wholly owned Subsidiaries: (a) unrestricted cash, and (b) cash equivalents consisting of (i) marketable, direct obligations of the United States of America, its agencies and instrumentalities maturing within three hundred sixty-five (365) days of the date of purchase, (ii) commercial paper issued by corporations, each of which shall have a combined net worth of at least $1 billion and each of which shall be a domestic issuer, maturing within two hundred seventy (270) days from the date of the acquisition thereof, and rated in the highest grade by Moody’s Investors Service, Inc. or Standard and Poor’s Ratings Group, (iii) repurchase agreements, bankers’ acceptances, and certificates of deposit maturing within three hundred sixty-five (365) days of the date of purchase which are issued by, or time deposits maintained with, any United States national bank the deposits of which are insured by the Federal Deposit Insurance Corporation and having capital, surplus and undivided profits totaling more than $1 billion and rated “A” or better by Moody’s Investors Service, Inc. or Standard and Poor’s Ratings Group, and (iv) shares of any open-end investment company registered under the Investment Company Act of 1940, as amended, that invests all or

5

substantially all of its funds in the items described in clauses (i) through (iii), above.

(i) Section 1(a) of the Schedule of Additional Terms to the Credit Agreement is hereby deleted in its entirety and the following text inserted in lieu thereof:

Availability Period: (i) (A) Up to $40,000,000 (“Tranche A1”) and up to $10,000,000 (“Tranche B1”) will be available from the Closing Date to March 31, 2003 (“Tranche 1 Availability Termination Date”), and (B) up to $15,900,000 (“Tranche X”) will be available from the Closing Date until September 30, 2003 (“Tranche X Availability Termination Date”).

(ii)

(I) up to $14,800,000 (“Tranche A2”) and up to $5,700,000 (“Tranche B2”) will be available until March 31, 2004 (“Tranche 2 Availability Termination Date”) from the earlier of (A) the Tranche 1 Availability Termination Date or (B) the date upon which Tranches A1 and B1 shall have been fully drawn.

(II) an amount equal to the portion of Tranche A2 that is unused as of close of business on the Tranche 2 Availability Termination Date (“Tranche A2½”) and an amount equal to the portion of Tranche B2 that is unused as of close of business on the Tranche 2 Availability Termination Date (“Tranche B2½”) will be available from April 1, 2004 until March 31, 2005 (“Tranche 2½ Availability Termination Date”).

(iii) up to $15,200,000 (“Tranche A3”) and up to $3,800,000 (“Tranche B3”) will be available until December 31, 2005 (the “Tranche 3 Availability Termination Date”) from and after the earlier of (X) the Tranche 2½ Availability Termination Date or (Y) the date upon which Tranches A2½ and B2½ shall have been fully drawn, provided that, in each case, an aggregate amount of no less than $54,000,000 cash shall have been contributed to the equity capital of Borrower as of such date since March 31, 2002 and provided, further, that the Tranche 3 Availability Termination Date shall occur December 31, 2004 unless the Borrower shall have made a borrowing of a Tranche 3 Loan on or prior to such date.

6

Tranches A1, A2, A2½, A3, B1, B2, B2½, B3 and X are herein each referred to as a “Tranche”, individually, and the “Tranches”, collectively.

Availability under all Tranches terminates on March 31, 2005.

Tranche A1, Tranche B1 and Tranche X are hereinafter referred to as “Tranche 1,” and any Loans outstanding under Tranche 1 are hereinafter referred to as “Tranche 1 Loans.” Tranche A2 and Tranche B2 are hereinafter referred to as “Tranche 2,” and any Loans outstanding under Tranche 2 are hereinafter referred to as “Tranche 2 Loans.” Tranche A2½ and Tranche B2½ are hereinafter referred to as “Tranche 2½,” and any Loans outstanding under Tranche 2½ are hereinafter referred to as “Tranche 2½ Loans.” Tranche A3 and Tranche B3 are hereinafter referred to as “Tranche 3,” and any Loans outstanding under Tranche 3 are hereinafter referred to as “Tranche 3 Loans.”

Tranches A1 through A3 are hereinafter referred to as “Tranche A,” and any Loans outstanding under Tranche A are hereinafter referred to as “Tranche A Loans.” Tranches B1 through B3 are hereinafter referred to as “Tranche B,” and any Loans outstanding under Tranche B are hereinafter referred to as “Tranche B Loans.” Any Loans outstanding under Tranche X are hereinafter referred to as “Tranche X Loans.”

The last Banking Day on which Loans are available hereunder is referred to as the “Commitment Expiry Date”; the Tranche 1 Availability Termination Date, the Tranche 2 Availability Termination Date, the Tranche 2½ Availability Termination Date, the Tranche 3 Availability Termination Date and the Tranche X Availability Termination Date are each referred to as a “Tranche Termination Date” and the period from the Closing Date to the Commitment Expiry Date is referred to as the “Availability Period.”

(j) Section 1(c) of the Schedule of Additional Terms to the Credit Agreement is hereby deleted in its entirety and the following text inserted in lieu thereof:

Commitment: $105,400,000.

(k) Section 2(a) of the Schedule of Additional Terms to the Credit Agreement is hereby deleted in its entirety and the following text inserted in lieu thereof:

Use of Proceeds: (i) Up to $70,000,000 under Tranche A for the financing of Borrower’s purchase of Cisco Systems networking and telecommunications equipment (and any software that is an

7

integral part thereof), including integrated access devices, from the Vendor thereof and the conversion of Tranche A Loans outstanding under the March 2002 Credit Agreement into Tranche A Loans under this Agreement; (ii) up to $19,500,000 under Tranche B for the financing of any standalone Cisco Systems software products and any other soft costs of Borrower incurred from Cisco Systems or other provider (other than any principal competitor of Cisco Systems) associated with the integration and installation of Cisco Systems networking and telecommunications equipment, and the conversion of Tranche B Loans outstanding under the March 2002 Credit Agreement into Tranche B Loans under this Agreement; provided that no more than $2,000,000 of said $19,500,000 may be borrowed for the purchase of echo cancellers, muxes and Agilent testing equipment (“Additional Gear”) and no Loan proceeds shall be paid to Borrower to reimburse Borrower for purchases of Additional Gear made by the Borrower prior to February 15, 2001; and (iii) up to $15,900,000 under Tranche X for the financing of accrued interest hereunder and the conversion of $5,000,000 of Tranche C Loans (as defined in the March 2002 Credit Agreement) outstanding under the March 2002 Credit Agreement into Tranche X Loans under this Agreement.

(l) Schedule 2(b) of the Schedule of Additional Terms to the Credit Agreement is hereby amended by replacing the word “Second” appearing therein with the word “Third” in lieu thereof.

(m) The Lender Annex and the cover page to the Credit Agreement are each hereby amended by replacing each occurrence of the amount “$115,400,000” appearing therein with the amount “$105,400,000” in lieu thereof.

SECTION 3 Conditions Precedent. The amendments contained in Section 2 shall become effective as provided in Section 5(a), provided that the following conditions shall have been satisfied on or prior to March 31, 2004 (the date upon which each of the following conditions are satisfied is referred to herein as the “Closing Date”):

(a) Agent shall have received from each party thereto a counterpart of (i) this Amendment, (ii) the Release, dated as of the Closing Date, by each Loan Party in favor of Cisco Systems and CSCC, (iii) Acknowledgement and Confirmation of Security Documents, dated as of the Closing Date, by each Loan Party and (iv) the Amended and Restated Warrant, with respect to up to 2,764,744 shares of Common Stock, dated the Closing Date by Holdings in favor of CSCC, substantially in the form attached hereto.

(b) There shall be no Default or Event of Default continuing as of the Closing Date under the Credit Agreement, as amended hereby, and Agent shall have received a certificate of a Responsible Officer of Holdings and Borrower, dated the Closing Date, to such effect.

8

(c) Agent shall have received the following, in form and substance satisfactory to Agent and each Lender: (i) evidence that all approvals or consents of any other Person, required in connection with the execution, delivery and performance of the Loan Documents shall have been obtained; (ii) a certificate of the Secretary or other appropriate officer of each Loan Party, dated the Closing Date certifying (A) copies of the Organization Documents of such Loan Party and the resolutions adopted by such Loan Party and other actions taken or adopted by such Loan Party authorizing the execution, delivery and performance of the Loan Documents, and (B) the incumbency, authority and signatures of each officer of such Loan Party authorized to execute and deliver the Loan Documents and act with respect thereto; and (iii) certificates of good standing with respect to each Loan Party certifying that each such Loan Party is qualified to do business and is in good standing in each jurisdiction in which the failure to so qualify or be in good standing would result in a Material Adverse Change.

(d) Certificate of the Loan Parties setting forth the capital structure of the Loan Parties, in form and substance satisfactory to the Agent and each Lender.

(e) Agent shall have received such Lien and judgment searches as Agent or any Lender shall have requested, and such termination statements or other documents as may be necessary to confirm that the Collateral described in the Collateral Documents is subject to no liens in favor of any Person (other than Permitted Liens).

(f) Agent shall have received legal opinions of legal counsel to the Loan Parties, dated the Closing Date, in form and substance satisfactory to Agent and each Lender.

(g) Agent shall have received, in form and substance satisfactory to Agent and each Lender, evidence of insurance coverage, together with evidence that Agent has been named as loss payee under all policies of property insurance and as additional insured under all policies of liability insurance, in each case as required by the Collateral Documents.

(h) Borrower shall have paid (i) all fees then due in accordance with the Fee Letter, (ii) all invoiced costs and expenses then due in accordance with Section 8.4 of the Credit Agreement and (iii) a restructuring fee to Lender in the amount of $239,750.

(i) Agent shall have received a Compliance Certificate (with respect to any of the financial covenants set forth in Section 5.1 in effect as of December 31, 2003) and an Update Certificate, each completed by a Responsible Officer of Holdings and Borrower, as of the end of the fiscal quarter immediately preceding the Closing Date.

(j) The parties hereto shall have delivered to Agent all other information and/or documentation reasonably requested by Agent.

SECTION 4 General Representations and Warranties. Borrower, Additional Borrower and Holdings each hereby represents and warrants to Agent that each of the representations and warranties of such party contained in the Credit Agreement (as amended hereby) are true and correct in all material respects as of the date hereof and Agent shall be entitled to rely on such representations and warranties as if they were made to Agent in this Amendment as of the date hereof.

9

SECTION 5 Miscellaneous.

(a) Effectiveness of this Amendment. The amendments set forth in Section 2 hereof shall become effective on the Closing Date, provided, however, that the amendment set forth in Section 2(h) shall, on the Closing Date, become effective as of November 2, 2002.

(b) Credit Agreement Otherwise Not Affected. Except as expressly amended pursuant hereto, the Credit Agreement shall remain unchanged and in full force and effect and is hereby ratified and confirmed in all respects. Agent’s execution and delivery of, or acceptance of, this Amendment and any other documents and instruments in connection herewith (collectively, the “Amendment Documents”) shall not be deemed to create a course of dealing or otherwise create any express or implied duty by it to provide any other or further amendments, consents or waivers in the future.

(c) No Reliance. Each of Borrower and Additional Borrower hereby acknowledges and confirms to Agent that Borrower is executing this Amendment and the other Amendment Documents on the basis of its own investigation and for its own reasons without reliance upon any agreement, representation, understanding or communication by or on behalf of any other Person.

(d) Binding Effect. This Amendment shall be binding upon, inure to the benefit of and be enforceable by Borrower, Additional Borrower, Agent, Holdings and their respective successors and assigns.

(e) Governing Law. This Agreement shall be governed by, and construed in accordance with, the law of the State of New York.

(f) Complete Agreement; Amendments. This Amendment, together with the other Loan Documents, contains the entire and exclusive agreement of the parties hereto and thereto with reference to the matters discussed herein and therein. This Amendment supersedes all prior commitments, drafts, communications, discussions and understandings, oral or written, with respect thereto. This Amendment may not be modified, amended or otherwise altered except in accordance with the terms of Section 8.1 of the Credit Agreement.

(g) Severability. Whenever possible, each provision of this Amendment shall be interpreted in such manner as to be effective and valid under all applicable laws and regulations. If, however, any provision of this Amendment shall be prohibited by or invalid under any such law or regulation in any jurisdiction, it shall, as to such jurisdiction, be deemed modified to conform to the minimum requirements of such law or regulation, or, if for any reason it is not deemed so modified, it shall be ineffective and invalid only to the extent of such prohibition or invalidity without affecting the remaining provisions of this Amendment, or the validity or effectiveness of such provision in any other jurisdiction.

(h) Counterparts. This Amendment may be executed in any number of counterparts and by different parties hereto in separate counterparts, each of which when so executed shall be deemed to be an original and all of which taken together shall constitute but one and the same agreement.

10

(i) Interpretation. This Amendment and the other Amendment Documents are the result of negotiations between and have been reviewed by counsel to Agent, Borrower and Holdings, and are the product of all parties hereto. Accordingly, this Amendment and the other Amendment Documents shall not be construed against Agent or any Lender merely because of Agent’s involvement in the preparation thereof.

(j) Loan Documents. This Amendment shall constitute a Loan Document.

[Remainder of page intentionally left blank.]

11

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

12