AMENDMENT TO THE EMPLOYMENT AGREEMENT BETWEEN CBEYOND, INC. AND J. ROBERT FUGATE

Exhibit 10.16

AMENDMENT

TO THE

EMPLOYMENT AGREEMENT BETWEEN

CBEYOND, INC. AND J. ROBERT FUGATE

This Amendment (this “Amendment”) to that certain Employment Agreement between Cbeyond, Inc. (the “Company”) and J. Robert Fugate (the “Executive”) dated as of March 10, 2008 (the “Employment Agreement”) is made as of this 31^st day of December, 2008 (the “Amendment Date”), by and among the Company and the Executive. Except as set forth is this Amendment, capitalized terms used herein but not defined herein shall have the meanings ascribed to them in the Employment Agreement.

WITNESSETH

WHEREAS, the Company and the Executive desire to amend the terms of the Employment Agreement as a result of Section 409A of the Internal Revenue Code of 1986, as amended;

NOW, THEREFORE, for good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the Executive and the Company (collectively the “Parties”) hereby agree as of the Amendment Date to the following:

1. Amendments to the Employment Agreement. Effective as of the Amendment Date, the Employment Agreement is hereby amended as follows:

(a) Section 2(a)(i) of the Employment Agreement is amended to read in full as follows:

“(i) Non-Change in Control Severance. Subject to Section 2(d) below, in the event of a Specified Termination of Executive’s employment, the Company shall in accordance with the customary payroll practices of the Company, during the period beginning the day after the date of Executive’s Separation from Service with the Company and ending on the first anniversary of such date, pay Executive severance payments to be paid at a rate equal to 100% of the annual base salary rate in effect immediately prior to Executive’s termination of employment. If Executive’s Specified Termination occurs following a Change in Control, the severance provisions of paragraph 2(a)(ii) shall control rather than the provisions of this paragraph.”

(b) Section 2(a)(ii) of the Employment Agreement is amended to read in full as follows:

“(ii) Post Change in Control Severance. Subject to Section 2(d) below, in the event of a Specified Termination of Executive’s employment following a Change in Control, in lieu of the severance described in paragraph 2(a)(i), above, the Company shall in accordance with the customary payroll practices of the Company, during the period beginning the day after the date of Executive’s Separation from Service and ending on the first anniversary of such date, pay Executive

severance payments to be paid at a rate equal to 100% of the annual base salary rate in effect immediately prior to Executive’s termination of employment. In addition, Company shall, within three business days of the date six months following the date of Executive’s Separation from Service, pay Executive a lump sum equal to the average of the bonus paid to the Executive by the Company over the previous three years plus, at Executive’s election, either (A) an additional lump sum equal to 50% of the annual base salary of the Executive in effect on the date of his Specified Termination or (B) no additional lump sum. If Executive chooses option (A), above, the Noncompete Period described in paragraph 3(d) below, shall be modified for all purposes under this Agreement to be equal to the period beginning on the date of Executive’s Specified Termination and ending eighteen months later.”

(c) Section 2(d) of the Employment Agreement is amended to read in full as follows:

“(d) Release; First Payment Date; Separate Payments. On or after the date of Executive’s Separation from Service and on or before the date that is 45 days after the date of Executive’s Separation from Service, Executive shall execute a release (the “Release”) in the form attached hereto and incorporated herein as Exhibit A or Exhibit B, as applicable. Such Release shall specifically relate to all of Executive’s rights and claims in existence at the time of such execution and shall confirm Executive’s obligations under Section 3 of this Agreement. It is understood that, if specified in the applicable Release, Executive has a certain number of calendar days to consider whether to execute such Release, and Executive may revoke such Release within seven (7) calendar days after execution. In the event Executive does not execute such Release within the period specified in the first sentence of this Section 2(d), or if Executive revokes such Release within the subsequent seven (7) day period, no benefits shall be payable under this Agreement. Notwithstanding anything to the contrary in this Agreement, any severance payments or benefits that would otherwise be payable or provided under this Agreement before the first normal payroll payment date falling on or after the sixtieth (60^th) day after the date on which the Executive incurs a Separation from Service (the “First Payment Date”) shall be made on the First Payment Date. Each separate severance installment payment and each other payment that Executive may be eligible to receive under this Agreement shall be a separate payment under this Agreement for all purposes.”

(d) The definition of “Good Reason” in the Employment Agreement is amended to read in full as follows:

“Executive shall have resigned for “Good Reason” if the Company, without Executive’s prior written consent: (i) significantly reduces the responsibilities and/or duties of Executive, excluding for this purpose an isolated, insubstantial and inadvertent action not taken in bad faith and which is remedied by the Company promptly after receipt of notice thereof given by Executive; (ii) materially reduces Executive’s base salary except that this clause shall not apply if the

2

salary reduction is of not more than 10% and is applicable to all Company executives above the rank of Vice President, (iii) materially reduces Executive’s bonus opportunity except that this clause shall not apply if the bonus opportunity reduction is applicable to all Company executives above the rank of Vice President, (iv) materially reduces the aggregate benefits provided to Executive, or (v) changes the location of Executive’s office to a location which is fifty (50) miles or more from the office where Executive is located on the date hereof. “Good Reason” shall also include the failure of a successor to the Company to assume this Agreement. Notwithstanding the foregoing, there shall be no resignation for Good Reason unless (i) Executive provides the Company written notice describing in reasonable detail the circumstances alleged to constitute Good Reason within 90 days of the first occurrence of such circumstances, (ii) the Company fails to cure such circumstances within 30 days following receipt of such written notice, and (iii) Executive’s resignation becomes effective and Executive incurs a Separation from Service within a reasonable period of time after the first occurrence of such circumstances (but in no event later than 2 years after the first occurrence of such circumstances).”

(e) The following definition is added to Section 3 (Definitions) of the Employment Agreement:

“‘Separation from Service’ means the Executive’s “separation from service” with the Company as such term is defined in Treasury Regulation Section 1.409A-1(h) and any successor provision thereto.”

(f) The definition of “Specified Termination” in the Employment Agreement is amended to read in full as follows:

“‘Specified Termination’ means a termination of Executive’s employment by the Company without Cause or the resignation of Executive for Good Reason, provided, however, that no Specified Termination shall occur unless the Executive also incurs a Separation from Service.”

(g) Section 4(l) of the Employment Agreement is amended to read in full as follows:

“(l) Code Section 409A.

(i) Six Month Delay. To the extent any benefits under this Agreement are treated as non-qualified deferred compensation subject to Section 409A of the Internal Revenue Code of 1986, as amended (the “Code”), then if Executive is deemed at the time of his Separation from Service to be a “specified employee” for purposes of Section 409A(a)(2)(B)(i) of the Code, then to the extent delayed commencement of any portion of the benefits to which Employee is entitled under this Agreement is required in order to avoid a prohibited distribution under Section 409A(a)(2)(B)(i) of the Code, such portion of Employee’s termination benefits shall not be provided to Employee prior to the earlier of (i) the expiration of the six-month period measured from the date of the Executive’s Separation from Service or (ii) the date of Executive’s death.

3

Upon the earlier of such dates, all payments deferred pursuant to this Section 3(f) shall be paid in a lump sum to Executive. Thereafter, payments will resume in accordance with this Agreement. The determination of whether the Executive is a “specified employee” for purposes of Section 409A(a)(2)(B)(i) of the Code as of the time of his Separation from Service shall made by the Company in accordance with the terms of Section 409A of the Code and applicable guidance thereunder (including without limitation Treas. Reg. Section 1.409A-1(i) and any successor provision thereto).

(ii) In-kind Benefits and Reimbursements. Notwithstanding anything to the contrary in this Agreement, in-kind benefits and reimbursements provided under this Agreement during any tax year of the Executive shall not affect in-kind benefits or reimbursements to be provided in any other tax year of the Executive, except for the reimbursement of medical expenses referred to in Section 105(b) of the Code, and are not subject to liquidation or exchange for another benefit. Notwithstanding anything to the contrary in this Agreement, reimbursement requests must be timely submitted by Executive and, if timely submitted, reimbursement payments shall be made to the Executive as soon as administratively practicable following such submission, but in no event later than December 31^st of the calendar year following the calendar year in which the expense was incurred. In no event shall the Executive be entitled to any reimbursement payments after December 31^st of the calendar year following the calendar year in which the expense was incurred. This paragraph shall only apply to in-kind benefits and reimbursements that would result in taxable compensation income to the Executive.

(iii) Miscellaneous. This Agreement is intended to be written, administered, interpreted and construed in a manner such that no payment or benefits provided under the Agreement become subject to (a) the gross income inclusion set forth within Code Section 409A(a)(1)(A) or (b) the interest and additional tax set forth within Code Section 409A(a)(1)(B) (together, referred to herein as the “Section 409A Penalties”), including, where appropriate, the construction of defined terms to have meanings that would not cause the imposition of Section 409A Penalties. In no event shall the Company be required to provide a tax gross-up payment to Executive or otherwise reimburse Executive with respect to Section 409A Penalties. Additionally, in the event that following the date hereof the Company or the Executive reasonably determines that any compensation or benefits payable under this Agreement may be subject to Section 409A of the Internal Revenue Code, the Company and the Executive shall work together to adopt such amendments to this Agreement or adopt other policies or procedures (including amendments, policies and procedures with retroactive effect), or take any other commercially reasonable actions necessary or appropriate to (x) exempt the compensation and benefits payable under this Agreement from Section 409A of the Code and/or preserve the intended tax treatment of the compensation and benefits provided with respect to this Agreement or (y) comply with the requirements of Section 409A of the Code and related Department of Treasury guidance.

4

2. No Other Amendment. Except as expressly set forth in this Amendment, the Employment Agreement shall remain unchanged and shall continue in full force and effect according to its terms.

3. Acknowledgement. The Executive acknowledges and agrees that he has carefully read this Amendment in its entirety, fully understands and agrees to its terms and provisions and intends and agrees that it be final and legally binding on the Executive and the Company.

4. Governing Law; Counterparts. This Amendment shall be construed in accordance with the laws of the State of Georgia without reference to principles of conflicts of law and may be executed in several counterparts by the Parties.

[Signature Page Follows]

5

IN WITNESS WHEREOF, the Executive has hereunto set the Executive’s hand and the Company has caused this Amendment to be executed in its name on its behalf, all as of the day and year first above written.

6