AMENDMENT NO. 2 TO REGISTRATION RIGHTS AGREEMENT

Exhibit 10.4

AMENDMENT NO. 2

TO

REGISTRATION RIGHTS AGREEMENT

AMENDMENT NO. 2 TO REGISTRATION RIGHTS AGREEMENT (this “Amendment”), dated as of September 8, 2004, made among ITC^DeltaCom, Inc., a Delaware corporation (the “Company”), and each Person listed on the signature pages hereof under the heading “Series A Preferred Stockholders” (collectively, the “Series A Preferred Stockholders”).

WITNESSETH:

WHEREAS, pursuant to the Agreement and Plan of Merger, dated as of the date hereof (as amended from time to time, the “FD Merger Agreement”), among the Company, Boatramp Co., a Delaware corporation and wholly owned subsidiary of the Company, Florida Digital Network, Inc., a Delaware corporation (“FD”), and certain stockholders of FD, the Company has agreed to consummate a business combination with FD by the merger of Boatramp Co. with and into FD;

WHEREAS, in connection with the consummation of such business combination, the Company will issue to the former stockholders of FD shares of the common stock, par value $0.01 per share, of the Company (the “Common Stock”);

WHEREAS, the Company wishes to enter into, as of the closing of the FD business combination, a registration rights agreement (the “FD Registration Rights Agreement”) among the Company and certain of the former stockholders of FD, pursuant to which the FD Holders (as defined below) will be entitled to certain demand and piggyback registration rights; and

WHEREAS, the parties to this Amendment wish to amend the Registration Rights Agreement, dated as of October 29, 2002, as amended and restated as of October 6, 2003 and as further amended as of December 4, 2003 (the “Agreement”), among the Company and the Series A Preferred Stockholders to facilitate the execution, delivery and performance of the FD Registration Rights Agreement;

NOW, THEREFORE, in consideration of the premises and the mutual covenants and conditions hereinafter set forth, and for other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the parties hereby agree as follows:

1. Effectiveness. This Amendment shall become effective as of the Effective Time (as such term is defined in the FD Merger Agreement) without any further action by the parties hereto, provided that (i) the Effective Time shall occur on a date which is not later than March 8, 2005 and (ii) the FD Registration Rights Agreement and Amendment No. 2 to the WCAS Registration Rights Agreement, in the forms attached as Exhibit C and Exhibit L, respectively, to the Merger Agreement, or in such other forms as the Holders shall have approved in writing, shall each have become effective as of the Effective Time.

2. Definitions. (a) All capitalized terms not defined in this Amendment (including the preamble and recitals hereof) shall have the meanings given to such terms in the Agreement.

(b) Each of the following terms is defined as follows:

“FD Holder” means any holder of FD Registrable Common Shares.

“FD Registrable Common Shares” means, with respect to any offering hereunder, the “Registrable Common Shares” (as defined in the FD Registration Rights Agreement) that the “Holders” (as defined in the FD Registration Rights Agreement) are entitled to request be included in such offering pursuant to the FD Registration Rights Agreement as in effect on the date hereof.

“FD Registration Rights Agreement” means the Registration Rights Agreement, dated as of [                        ], among the Company and the other Persons listed on the signature pages thereof.

“Rule 144A Resale Shelf Registration” means a registration under the Securities Act of convertible notes, preferred stock and/or warrants for resale of such securities by the purchasers thereof acquired in an offering under the Securities Act made to one or more nationally recognized investment banking firms as initial purchasers for reoffering by such initial purchasers solely to “qualified institutional buyers” (as defined in Rule 144A under the Securities Act), to other institutional “accredited investors” (as defined in Rule 501(a)(1), (2), (3) or (7) under the Securities Act), or to investors outside the United States in compliance with Regulation S under the Securities Act.

(c) The definition of “Excluded Registration” set forth in Section 1 of the Agreement is hereby amended and restated in its entirety to read as follows:

“‘Excluded Registration’ means (a) a registration of Common Stock under the Securities Act pursuant to a registration statement filed (i) on Form S-4 or Form S-8 or any successor registration forms that may be adopted by the SEC or (ii) in connection with an exchange offer or an offering of securities solely to existing stockholders of the Company or employees of the Company or its subsidiaries, or (b) a Rule 144A Resale Shelf Registration.”

(d) The definition of “Other Registrable Securities” set forth in Section 1 of the Agreement is hereby amended and restated in its entirety to read as follows:

“‘Other Registrable Securities’ means, with respect to any offering hereunder, the securities that any Person is entitled to request be included in such offering pursuant to any registration rights agreement other than this Agreement, the WCAS Registration Rights Agreement or the FD Registration Rights Agreement.”

-2-

3. Amendment to Section 2. Section 2 of the Agreement is hereby amended and restated in its entirety to read as follows:

“2. Securities Subject to this Agreement. The Registrable Securities are the sole securities entitled to the benefits of this Agreement. For the purposes of this Agreement, and except as expressly provided in this Section 2, Registrable Securities held by any Holder shall cease to be Registrable Securities (and such Holder shall cease to have any registration rights with respect to such securities under this Agreement) on the date and to the extent that (i) a Registration Statement covering such Registrable Securities has been declared effective under the Securities Act and such Registrable Securities have been disposed of pursuant to such effective Registration Statement, (ii) such Registrable Securities have been sold or transferred in accordance with the requirements of Rule 144, (iii) such Registrable Securities have been otherwise transferred or disposed of, certificates therefor not bearing a legend restricting further transfer or disposition thereof shall have been delivered by the Company and, at such time, subsequent transfer or disposition of such securities shall not require registration of such securities under the Securities Act, (iv) unless such Holder is SCANA or an Affiliate of SCANA, all Registrable Securities then owned by such Holder may be sold or transferred by such Holder without holding period, volume or manner of offering limitations under the Securities Act and the rules and regulations thereunder, (v) unless such Holder is SCANA or an Affiliate of SCANA, all Registrable Securities then owned by such Holder may be sold or transferred by such Holder within any three-month period in accordance with the requirements of Rule 144 or (vi) such Registrable Securities have ceased to be outstanding.”

4. Underwritten Offerings. Notwithstanding the provisions of Section 3(c) or Section 4(c) of the Agreement, the Plan of Distribution attached as Exhibit A to the Agreement or any other provision of the Agreement, as amended, each Series A Preferred Stockholder hereby irrevocably waives the right of such Series A Preferred Stockholder to demand an Underwritten Offering under the Shelf Registration Statement pursuant to Section 4(c) or any other provision of the Agreement.

5. Demand Registrations. Section 4(f) of the Agreement is hereby amended and restated in its entirety to read as follows:

“(f) Subject to Section 4(g), a registration requested pursuant to this Section 4 shall not be deemed to be effected for purposes of this Section 4: (i) if the Registration Statement for such registration has not been declared effective by the SEC or become effective in accordance with the Securities Act and the rules and regulations thereunder; (ii) in the case of a Registration Statement which does not contemplate an Underwritten Offering, if such Registration Statement does not remain effective for at least 120 days (or such shorter period that will terminate when all Registrable Securities covered by such Registration Statement have been sold or withdrawn); (iii) in the case of a Registration Statement which contemplates an Underwritten Offering, if (A) such Registration Statement does not remain effective for at least 120 days plus such longer period (not to exceed 90 days after the 120th day) as, in the opinion of counsel for the underwriter or underwriters, is required by law for the delivery of a Prospectus in connection with the sale of Registrable Securities by an underwriter or dealer, or (B) the conditions to closing specified in the applicable underwriting agreement are not satisfied by reason of a violation or breach

-3-

of such underwriting agreement or this Agreement by the Company; or (iv) if, as a result of a determination made by the lead managing underwriter or (if the offering shall not be an Underwritten Offering) the Holders pursuant to Section 6(a), the Holders shall not be entitled to include at least 75% of the Registrable Securities that such Holders requested pursuant to Section 4(a) to be so included in such registration (calculated on an as-converted basis, assuming that all Registrable Securities requested for inclusion in such registration that are convertible into or exercisable for Common Stock are converted into or exercised for Common Stock).”

6. Cutbacks. Section 6 of the Agreement is hereby amended and restated in its entirety to read as follows:

“6. Cutbacks.

(a) Offerings by the Holders, the WCAS Stockholders or the FD Holders. In connection with any offering covered by a Registration Statement filed pursuant to Section 4 of this Agreement, Section 4 of the WCAS Registration Rights Agreement or Section 3 of the FD Registration Rights Agreement, if the lead managing underwriter or (if the offering shall not be an Underwritten Offering) the Holders, the WCAS Stockholders or the FD Holders who have exercised a demand registration to initiate such offering give written notice (a “Cutback Notice”) to the Company (it being understood that the Company shall as soon as reasonably practicable deliver copies of any such notice that has not been made by the Holders to all Holders who have requested to include Registrable Securities in such offering) that, in its or their reasonable and good faith opinion, the Registrable Securities, the WCAS Registrable Securities and the FD Registrable Common Shares requested to be included in such offering exceed the number which can be sold in such offering without being likely to have a significant adverse effect on the offering price, timing or distribution of the class of securities offered, on the market for the securities offered or on the market for the Common Stock (an “Adverse Offering Effect”), then the Company shall include in such offering only the number of Registrable Securities, WCAS Registrable Securities and FD Registrable Common Shares which, in the good faith opinion of such underwriter or (if the offering shall not be an Underwritten Offering) the Holders, the WCAS Stockholders or the FD Holders who have exercised a demand registration to initiate such offering, as the case may be, can be included without having an Adverse Offering Effect. In such event, the shares of Common Stock and other securities to be included in such offering shall consist of (i) first, all of the Registrable Securities that the Holders propose to sell pursuant to Section 4 or 5, all of the WCAS Registrable Securities that the WCAS Stockholders propose to sell pursuant to Section 4 or 5 of the WCAS Registration Rights Agreement and all of the FD Registrable Common Shares that the FD Holders propose to sell pursuant to Section 3 or 4 of the FD Registration Rights Agreement (with any reduction in such number being allocated among the Holders, the WCAS Stockholders and the FD Holders pro-rata based on the number, as of the date of delivery of the first Cutback Notice delivered to the Holders, the WCAS Stockholders and the FD Holders in connection with such offering, of shares of Common Stock represented by the

-4-

Registrable Securities, the WCAS Registrable Securities or the FD Registrable Common Shares, as the case may be, requested by the Holders, the WCAS Stockholders and the FD Holders to be included in such offering, calculated on an as-converted basis assuming that all of the Registrable Securities of the Holders and all of the WCAS Registrable Securities of the WCAS Stockholders requested to be so included that are convertible into or exercisable for Common Stock are converted into or exercised for Common Stock as of such date), (ii) second, the number, if any, of shares of Common Stock or other securities the Company proposes to sell for its own account that, in the reasonable and good faith opinion of such lead managing underwriter or (if the offering shall not be an Underwritten Offering) the Holders, the WCAS Stockholders or the FD Holders who have exercised a demand registration to initiate such offering can be sold without having an Adverse Offering Effect, and (iii) third, the number, if any, of other shares of Common Stock and other securities requested to be included in such offering that, in the reasonable and good faith opinion of such lead managing underwriter or (if the offering shall not be an Underwritten Offering) the Holders, the WCAS Stockholders or the FD Holders who have exercised a demand registration to initiate such offering can be sold without having an Adverse Offering Effect, such other shares of Common Stock and other securities to be allocated among the holders thereof who have requested that their shares and other securities be so included in accordance with the provisions of their registration rights agreements with the Company.

(b) Offerings by the Company. Each Holder wishing to include Registrable Securities pursuant to Section 5(a) in any offering covered by a Registration Statement filed by the Company relating to a public offering of Common Stock or other securities for its own account (other than in connection with an Excluded Registration) shall have the right to include such Registrable Securities in any such offering only to the extent that the inclusion of such Registrable Securities shall not reduce the number of shares of Common Stock or other securities to be offered and sold therein by the Company for its own account. In connection with the inclusion of Registrable Securities pursuant to Section 5(a) in any such offering by the Company, if the lead managing underwriter in an Underwritten Offering delivers a Cutback Notice to the Company (it being understood that the Company shall as soon as reasonably practicable deliver copies of any such notice to all Holders who have requested to include Registrable Securities in such offering) or (if the offering shall not be an Underwritten Offering) the Company delivers a Cutback Notice to the Holders, then the Company shall include in such offering, in addition to the securities the Company proposes to sell for its own account, only the aggregate number of securities that, in the reasonable and good faith opinion of such lead managing underwriter or (if the offering shall not be an Underwritten Offering) the Company, can be included without having an Adverse Offering Effect. Such aggregate number of securities to be included in such offering shall be allocated on a pro rata basis among (i) the Holders who have requested Registrable Securities be so included, (ii) the WCAS Stockholders who have requested WCAS Registrable Securities be so included and (iii) the FD Holders who have requested FD Registrable Common Shares be so included, based on the number,

-5-

as of the date of delivery of the first Cutback Notice delivered to the Holders, the WCAS Stockholders and the FD Holders in connection with such offering, of shares of Common Stock represented by the Registrable Securities, the WCAS Registrable Securities or the FD Registrable Common Shares, as the case may be, requested by the Holders, the WCAS Stockholders and the FD Holders to be included in such offering, calculated on an as-converted basis assuming that all of the Registrable Securities of the Holders and all of the WCAS Registrable Securities of the WCAS Stockholders requested to be so included that are convertible into or exercisable for Common Stock are converted into or exercised for Common Stock as of such date. No other securities shall be included in such offering except to the extent that, in the reasonable and good faith opinion of such lead managing underwriter or (if the offering shall not be an Underwritten Offering) the Company, such securities can be included without having an Adverse Offering Effect.

(c) Other Offerings In connection with any offering described in Section 5(a), other than an offering covered by a Registration Statement filed pursuant to Section 4 of this Agreement, Section 4 of the Series A Registration Rights Agreement or Section 3 of the FD Registration Rights Agreement, or an offering by the Company for its own account, if the lead managing underwriter (if the offering shall be an Underwritten Offering) or the Initiating Securityholder (if the offering shall not be an Underwritten Offering) delivers a Cutback Notice to the Company (it being understood that the Company shall as soon as reasonably practicable deliver copies of any such notice to all Holders who have requested to include Registrable Securities in such offering), then the Company shall include in such offering only the number of Registrable Securities, WCAS Registrable Securities, FD Registrable Common Shares and Other Registrable Securities which, in the good faith opinion of such underwriter or the Initiating Securityholders, as the case may be, can be included without having an Adverse Offering Effect. In such event, the shares of Common Stock and other securities to be included in such offering shall consist of (i) first, all of the Registrable Securities that the Holders propose to sell pursuant to Section 5, all of the WCAS Registrable Securities that the WCAS Stockholders propose to sell pursuant to Section 5 of the WCAS Registration Rights Agreement, all of the FD Registrable Common Shares that the FD Holders propose to sell pursuant to Section 4 of the FD Registration Rights Agreement and all Other Registrable Securities that the Initiating Securityholders propose to sell (with any reduction in such number being allocated pro-rata based on the number, as of the date of delivery of the first Cutback Notice delivered to the Holders, the WCAS Stockholders and the FD Holders in connection with such offering, of shares of Common Stock represented by the Registrable Securities, the WCAS Registrable Securities or the FD Registrable Common Shares, as the case may be, requested by the Holders, the WCAS Stockholders and the FD Holders to be included in such offering, calculated on an as-converted basis assuming that all of the Registrable Securities of the Holders and all of the WCAS Registrable Securities of the WCAS Stockholders requested to be so included that are convertible into or exercisable for Common Stock are converted into or exercised for Common Stock as of such date), (ii) second, the number, if any, of shares of Common Stock or other

-6-

securities the Company proposes to sell for its own account that, in the reasonable and good faith opinion of such lead managing underwriter or the Initiating Securityholders, as applicable, can be sold without having an Adverse Offering Effect, and (iii) third, the number, if any, of other shares of Common Stock and other securities requested to be included in such offering that, in the reasonable and good faith opinion of such lead managing underwriter or the Initiating Securityholders, as applicable, can be sold without having an Adverse Offering Effect, such other shares of Common Stock and other securities to be allocated among the holders thereof who have requested that their shares and other securities be so included in accordance with the provisions of their registration rights agreements with the Company.”

7. No Inconsistent Agreements; Most Favorable Provisions. Section 15 of the Agreement is hereby amended and replaced in its entirety to read as follows:

“15. No Inconsistent Agreements; Most Favorable Provisions. The Company is not currently a party to, and after the date hereof shall not enter into, any agreement which is inconsistent with the rights granted to the Holders of Registrable Securities by this Agreement. The Holders agree for purposes of this Section 15 that (i) the WCAS Registration Rights Agreement, as amended as of the date hereof by Amendment No. 1 and Amendment No. 2 thereto, and (ii) the FD Registration Rights Agreement in the form attached hereto as Exhibit B are not inconsistent with the rights of the Holders hereunder. If the Company shall (A) further amend the WCAS Registration Rights Agreement, (B) amend the FD Registration Rights Agreement or (C) enter into any agreement after the date hereof with any other Person, in each case, pursuant to which the WCAS Stockholders under the WCAS Registration Rights Agreement, the FD Holders under the FD Registration Rights Agreement or such other Person under such other agreement, as the case may be, shall have registration rights with respect to any security of the Company that are materially more favorable to the WCAS Stockholders, the FD Holders or such other Person, as the case may be, than those set forth in this Agreement, this Agreement shall thereupon, and without any further action on the part of any Holder or the Company, be deemed to be, and shall be, automatically amended to provide such materially more favorable rights to the Holders. Notwithstanding the foregoing provisions of this Section 15, this Section 15 shall not apply to, and shall not provide the Holders with any rights with respect to, any agreement relating to a Rule 144A Resale Shelf Registration.”

8. Assignment of Registration Rights. Section 16 of the Agreement is hereby amended and replaced in its entirety to read as follows:

“16. Assignment of Registration Rights. The right to cause the Company to register Registrable Securities pursuant to this Agreement may be assigned (but only with all related obligations hereunder) by any Holder in connection with a transfer of such Registrable Securities to any transferee who, immediately following such transfer, holds at least 5% of then-outstanding Registrable Securities (calculated on an as-converted basis, assuming that all

-7-

outstanding Registrable Securities that are convertible into or exercisable for Common Stock are converted into or exercised for Common Stock); provided that, as a condition to the effectiveness of such assignment, such transferee shall be required to execute a counterpart of this Agreement and each amendment to this Agreement. Upon such transferee’s execution of such counterparts, such transferee shall be deemed to be a Holder for all purposes of this Agreement and shall be entitled to the benefits of, and shall be subject to the restrictions contained in, this Agreement, as amended from time to time, as a Holder hereunder to the same extent as if such transferee had originally been included in the definition of a Holder and had originally been a party hereto.”

9. Miscellaneous. This Amendment shall not constitute an amendment or modification of any provision of the Agreement not expressly referred to herein. Except as expressly set forth in this Amendment, the terms, provisions and conditions of the Agreement shall remain unchanged and in full force and effect. This Amendment may be executed in counterparts, all of which shall together constitute a single agreement.

10. GOVERNING LAW. THIS AMENDMENT SHALL BE GOVERNED BY AND CONSTRUED IN ACCORDANCE WITH THE LAWS OF THE STATE OF NEW YORK WITHOUT GIVING EFFECT TO ITS PRINCIPLES OR RULES OF CONFLICT OF LAWS TO THE EXTENT SUCH PRINCIPLES OR RULES WOULD REQUIRE OR PERMIT THE APPLICATION OF THE LAWS OF ANOTHER JURISDICTION.

[signature pages follow]

-8-

IN WITNESS WHEREOF, the parties have executed this Amendment as of the date set forth in the first paragraph hereof.

-9-

-10-