AMENDED AND RESTATED STOCK SUBSCRIPTION WARRANT

Exhibit 10.8

THIS WARRANT AND THE COMMON STOCK PURCHASABLE HEREUNDER HAVE NOT BEEN REGISTERED UNDER THE SECURITIES ACT OF 1933, AS AMENDED, OR UNDER THE SECURITIES LAWS OF ANY STATE OR OTHER JURISDICTION, AND MAY NOT BE SOLD OR OFFERED FOR SALE OR OTHERWISE TRANSFERRED IN THE ABSENCE OF AN EFFECTIVE REGISTRATION STATEMENT AS TO THE SECURITIES UNDER SAID ACT AND ANY APPLICABLE STATE SECURITIES LAWS OR THE AVAILABILITY OF AN EXEMPTION FROM REGISTRATION UNDER SAID ACT AND ANY APPLICABLE STATE SECURITIES LAWS. THE OFFERING OF THIS SECURITY HAS NOT BEEN REVIEWED OR APPROVED BY ANY STATE SECURITIES ADMINISTRATOR.

AMENDED AND RESTATED STOCK SUBSCRIPTION WARRANT

To Purchase Common Stock of

Cbeyond Communications, Inc.

THIS CERTIFIES THAT for value received, CISCO SYSTEMS CAPITAL CORPORATION, a Nevada corporation, or its registered assigns (hereinafter called “Holder”) shall be entitled to receive from CBEYOND COMMUNICATIONS, INC., a Delaware corporation (“Company”), upon the exercise of this Warrant (which exercise shall happen automatically upon the occurrence of a Sale Trigger Event and upon the election of Holder in accordance with the terms hereof during the Post-Exercise Event Term, so long as such exercise occurs on or before March 31, 2010 (the “Expiration Date”)), a number of shares of common stock, $0.01 par value, of Company (the “Common Stock”) equal to the product of (x) 2,768,744, multiplied by (y) the Additional Equity Percentage, at the Warrant Price, payable as provided herein. The exercise of this Warrant shall be subject to the provisions, limitations and restrictions herein contained. After the earlier to occur of (x) a Qualified IPO and (y) a Tranche 3 Loan Drawdown, this Warrant may be exercised in whole or in part during the Post-Exercise Event Term. This Amended And Restated Stock Subscription Warrant replaces that certain Stock Subscription Warrant initially issued on November 1, 2002 covering 2,768,744 shares of Common Stock of the Company.

SECTION 1. Definitions.

For all purposes of this Warrant, the following terms shall have the meanings indicated (any capitalized terms used herein and not otherwise defined herein to have the meanings ascribed to them in the Agreement):

“Additional Equity Percentage” shall mean, as of the date of the Trigger Event, the then current Equity Value of Company minus $300 million divided by $100 million; provided, however, that, for purposes of the calculation of the Additional Equity Percentage, if the Equity Value of Company as of the date of the Trigger Event shall be greater than $400 million, the

Equity Value of Company shall be deemed to be $400 million. If the Equity Value of Company as of the date of the Trigger Event shall be $300 million or less, then the Additional Equity Percentage shall equal zero. In the event that the Trigger Event is the occurrence of a Tranche 3 Loan Drawdown, the Additional Equity Percentage shall be deemed to be 100%.

“Agreement” shall mean the Second Amended and Restated Credit Agreement dated as of November 1, 2002 among Company, the Borrower each Additional Borrower named therein, Holder, the other Lenders named therein and the Agent, as amended by Amendment No. 1, dated June 30, 2003, and as amended by Amendment No. 2, dated March 25, 2004, under which Holder and the other Lenders have agreed to make certain credit extensions to Company.

“Appraiser” shall mean an independent investment bank or other firm qualified to act as an appraiser and having experience in the telecommunications industry.

“Borrower” shall mean Cbeyond Communications LLC, a Delaware limited liability company and wholly-owned subsidiary of the Company, and a borrower under the Agreement.

“Equity Value” shall mean (i) in the event that the Trigger Event is a transaction described in subsection (a) of the definition of “Trigger Event”, the aggregate of any cash, marketable securities (the value of which shall be equal to average of the daily closing prices of such securities for the 15 consecutive business days ending on the last business day before the day in question) and other consideration (the fair market value of which shall be valued in good faith by the Board of the Company (the “Board”)) received by Company as consideration, less the liabilities of Company immediately after consummation of such transaction, (ii) in the event that the Trigger Event is a transaction described in subsection (b) of the definition of “Trigger Event”, the aggregate of any cash, marketable securities (the value of which shall be equal to average of the daily closing prices of such securities for the 15 consecutive business days ending on the last business day before the day in question) and other consideration (the fair market value of which shall be valued in good faith by the Board) received by the selling stockholders of Company pursuant to such transaction, and (iii) in the event that the Trigger Event is a Qualified IPO, the price per share of Common Stock as set forth in the Qualified IPO prospectus multiplied by the number of shares of Common Stock outstanding (on a fully diluted basis assuming the conversion or exercise of all securities convertible into or exercisable for Common Stock and including, without limitation, this Warrant) immediately prior to such Qualified IPO, plus the aggregate liquidation preference of all outstanding shares of preferred stock of Company immediately prior to such Qualified IPO that are not convertible into shares of Common Stock. With respect to any good faith valuation of the fair market value of consideration made by the Board in accordance with this definition, Holder shall have the right, within ten (10) days of its receipt of any such valuation, to give notice to Company that it disagrees with such valuation. Holder and Company shall then have ten (10) days from the date of such notice by Holder to discuss and mutually agree upon such valuation. If, upon the expiration such ten (10) day period, Holder and Company have not mutually agreed upon such valuation, then an appraisal of the fair market value of such consideration shall be conducted in accordance with this paragraph. The Appraiser shall be mutually agreed upon by Holder and Company within ten (10) days of the end of the ten (10) day period set forth in the previous sentence. In the event that Holder and

2

Company are unable to mutually agree upon the Appraiser within such ten (10) day period, then the Appraiser shall be selected by the President of the American Arbitration Association (the “AAA”) in New York, New York, who shall utilize the criteria set forth in the definition of “Appraiser” to make such a selection. Upon being selected by the parties or the President of the AAA, as the case may be, the Appraiser shall have twenty (20) days to make a determination with respect to the fair market value of the applicable consideration. Such valuation by the Appraiser shall be conclusive and binding on Holder and Company. All costs arising out of or related to such appraisal shall be borne by Holder.

“Exchange Act” shall mean the Securities Exchange Act of 1934, as amended from time to time.

“Exercise Event” shall mean the occurrence of either (x) a Qualified IPO, or (y) a Tranche 3 Loan Drawdown.

“Post-Exercise Event Term” shall mean the period beginning on the earlier to occur of (x) the date of a Qualified IPO, and (y) the date of a Tranche 3 Loan Drawdown and ending on the Expiration Date.

“Qualified IPO” shall mean a sale of Common Stock by Company or selling shareholders of Company in which (a) the Common Stock shall have been registered pursuant to an effective registration statement under the Securities Act, and (b) the aggregate net proceeds received by Company and the selling stockholders in connection with such registration statement equals or exceeds $50 million.

“Registration Rights Agreement” shall mean that certain Second Amended and Restated Registration Rights Agreement dated as of November 1, 2002, as amended, among Company, the Preferred Holders and the Common Holders.

“Sale Trigger Event” shall mean a Trigger Event which occurs in accordance with either subsection (a) or (b) of the definition of the term “Trigger Event.”

“Securities Act” shall mean the Securities Act of 1933, as amended from time to time.

“Tranche 3 Loan Drawdown” shall mean the drawdown and receipt by the Borrower of all or any portion of the proceeds of the Tranche 3 Loans, or any equipment or services provided by Cisco Systems, Inc. representing the proceeds of such Tranche 3 Loans.

“Tranche 3 Loans” shall have the meaning ascribed to such term in the Agreement.

“Trigger Event” shall mean any of (a) the sale, lease, transfer, conveyance or other disposition, in one or a series of related transactions, of all or substantially all of the assets of Company and its subsidiaries, taken as a whole (other than a collateral assignment by Company and its subsidiaries of such assets to any lender as security for Company’s and its subsidiaries obligations to such lender), (b) a merger, consolidation, sale of securities, recapitalization or similar transaction the result of which is that the beneficial owners of Company’s outstanding

3

voting stock immediately prior to the transaction cease to own directly or indirectly at least 50% of the voting power of the outstanding voting stock of Company or the surviving entity after consummation of such transaction(s), or (c) the date of an Exercise Event.

“Warrant Price” shall mean $0.01 per share, subject to adjustment in accordance with Section 6 hereof.

“Warrants” shall mean this Warrant and any other Warrant or Warrants issued to any transferees of such original holder or subsequent holder.

“Warrant Shares” shall mean shares of Common Stock, subject to adjustment or change as herein provided, purchased or purchasable by Holder upon the exercise hereof.

SECTION 2. Exercise of Warrant.

2.1 Procedure for Exercise of Warrant.

(a) Upon the occurrence of a Sale Trigger Event (but only in the event that the Sale Trigger Event occurs on or before the Expiration Date), this Warrant shall be automatically exercised and the Company shall issue to Holder that number of whole shares of Common Stock (or, if applicable, the consideration per whole share that holders of Common Stock are entitled to receive in the transaction constituting a Sale Trigger Event) computed using the formula set forth in subsection (d) below.

(b) If the Exercise Event is a Qualified IPO, then upon the occurrence of a Qualified IPO, the Holder shall have the right, during the Post-Exercise Event Term, to exercise this Warrant in whole or in part (but not as to any fractional share of Common Stock) by delivering to Company at its office referred to in Section 13 hereof at any time and from time to time during the Post-Exercise Event Term of this Warrant the Notice of Exercise in the form of Exhibit A attached hereto. In such event of a Qualified IPO, this Warrant shall be exercisable, in the aggregate for all exercises of this Warrant, for an aggregate of up to that number of whole shares of Common Stock computed using the formula set forth in subsection (d) below or, if the Holder elects to pay the Warrant Price in cash, the Holder shall receive, against such payment of the Warrant Price, the full number of whole shares of Common Stock issuable upon such exercise.

(c) If the Exercise Event is the occurrence of the Tranche 3 Loan Drawdown, then upon the occurrence of the Tranche 3 Loan Drawdown the Holder shall have the right, during the Post-Exercise Event Term, to exercise this Warrant in whole or in part (but not as to any fractional share of Common Stock) by delivering to Company at its office referred to in Section 13 hereof at any time and from time to time during the Post-Exercise Event Term of this Warrant the Notice of Exercise in the form of Exhibit A attached hereto. In such event of the occurrence of the Tranche 3 Loan Drawdown, this Warrant shall be exercisable, in the aggregate for all exercises of this Warrant, for an aggregate of up to 2,768,744 whole shares of Common Stock.

4

(d) The formula referred to in subsections (a) and (b) above shall be as follows:

Where

(e) In the event of any exercise (whether in accordance with subsections (a), (b) or (c) above) of the rights represented by this Warrant, a certificate or certificates for the shares of Common Stock so purchased (if applicable in the case of an exercise in accordance with subsection (a) above), registered in the name of Holder or, subject to compliance with Section 7.2, such other name or names as may be designated by Holder, shall be delivered to Holder hereof within a reasonable time, not exceeding fifteen (15) days after (i) the consummation of a Sale Trigger Event, or (ii) the exercise of such rights in accordance with subsections (b) or (c). The person in whose name any certificate for shares of Common Stock is issued upon such exercise shall for all purposes be deemed to have become the holder of record of such shares on the date of the such exercise, irrespective of the date of delivery of such certificate, except that, if the date of such compliance is a date when the stock transfer books of Company are closed, such person shall be deemed to have become the holder of such shares at the close of business on the next succeeding date on which the stock transfer books are open.

2.2 Transfer Restriction Legend. Each certificate for Warrant Shares shall bear the following legend (and any additional legend required by (i) any applicable state securities laws and (ii) any securities exchange upon which such Warrant Shares may, at the time of such exercise, be listed) on the face thereof unless at the time of exercise such Warrant Shares shall be registered under the Securities Act:

“The shares represented by this certificate have not been registered under the Securities Act of 1933, as amended, and may not be sold or transferred in the absence of such registration or an exemption therefrom under said Act.”

Any certificate issued at any time in exchange or substitution for any certificate bearing such legend (except a new certificate issued upon completion of a public distribution under a registration statement of the securities represented thereby) shall also bear such legend unless, in the opinion of counsel for Holder thereof (which counsel shall be reasonably satisfactory to Company) the securities represented thereby are not, at such time, required by law to bear such legend.

5

SECTION 3. Covenants as to Common Stock. Company covenants and agrees that all shares of Common Stock that may be issued upon the exercise of the rights represented by this Warrant shall, upon issuance, be validly issued, fully paid and nonassessable, and free from all taxes, liens and charges with respect to the issue thereof. The Company further covenants and agrees that it shall pay when due and payable any and all federal and state taxes (other than federal or state income taxes or similar laws) which may be payable in respect of the issue of this Warrant or any Common Stock or certificates therefor issuable upon the exercise of this Warrant, except that, if Warrant Shares or new Warrants shall be registered in a name or names other than the name of the Holder, funds sufficient to pay all transfer taxes payable as a result of such transfer shall be paid by the Holder at the time of delivery of the Notice of Exercise.

SECTION 4. Representations and Warranties Regarding Capitalization Issues. As of the initial issuance hereof, Company does not have outstanding any securities convertible into or exchangeable for, or any rights to subscribe for or to purchase, or any options or warrants for the purchase of, or any agreement providing for the issuance (contingent or otherwise) of, or any calls, commitments or claims of any character relating to, its capital stock, in each case other than as disclosed in writing to Holder prior to the date hereof.

SECTION 5. Adjustment of Number of Shares. Upon each adjustment of the Warrant Price as provided in Section 6 (other than clause (i) thereof), Holder shall thereafter be entitled to purchase, at the Warrant Price resulting from such adjustment, only the number of shares (calculated to the nearest tenth of a share) obtained by multiplying the Warrant Price in effect immediately prior to such adjustment by the number of shares purchasable pursuant hereto immediately prior to such adjustment and dividing the product thereof by the Warrant Price resulting from such adjustment.

SECTION 6. Adjustment of Warrant Price. The Warrant Price shall be subject to adjustment from time to time as follows:

(i) If Company shall at any time or from time to time during the period commencing on the date of issuance of this Warrant and ending upon the earlier to occur of (A) a Sale Trigger Event, (B) the exercise of the rights represented by this Warrant after the occurrence of Qualified IPO, or (B) March 31, 2010 (the “Adjustment Period”), issue shares of Common Stock other than Excluded Stock (as hereinafter defined) without consideration or for a consideration per share less than the Warrant Price in effect immediately prior to the issuance of such Common Stock, the Warrant Price in effect immediately prior to each such issuance shall forthwith (except as provided in this clause (i)) be adjusted to a price equal to the quotient obtained by dividing:

(A) an amount equal to the sum of

(x) the total number of shares of Common Stock outstanding (including any shares of Common Stock deemed to have been issued pursuant to subdivision (3) of this clause (i) and to clause (ii) below) immediately prior to such issuance multiplied by the Warrant Price in effect immediately prior to such issuance, plus

6

(y) the consideration received by Company upon such issuance,

by

(B) the total number of shares of Common Stock outstanding (including any shares of Common Stock deemed to have been issued pursuant to subdivision (3) of this clause (i) and to clause (ii) below) immediately after the issuance of such Common Stock.

For the purposes of any adjustment of the Warrant Price pursuant to this clause (i), the following provisions shall be applicable:

7

purchase or rights to subscribe for such convertible or exchangeable securities or obligations and subsequent conversions or exchanges thereof shall be deemed to have been issued at the time such securities or obligations were issued or such options or rights were issued and for a consideration equal to the consideration received by Company for any such securities or obligations and related options or rights (excluding any cash received on account of accrued interest or accrued dividends), plus the additional consideration, if any, to be received by Company upon the conversion or exchange of such securities or obligations or the exercise of any related options or rights (the consideration in each case to be determined in the manner provided in subdivisions (1) and (2) above with the proviso in subdivision (2) being applied to the number of shares of Common Stock deliverable upon such conversion, exchange or exercise);

(ii) “Excluded Stock” shall mean shares of Common Stock issued by the Company (1) as a stock dividend payable in shares of Common Stock or upon any subdivision or split up of the outstanding shares of Common Stock, under any of the circumstances for which an adjustment is provided in clauses (iii) or (iv) of this Section 6 or in Section 8, (2) in connection with the issuance of Common Stock (including any share of Common Stock deemed to have been issued pursuant to subdivision (3) of clause (i) above) under any stock option or other similar incentive plan or stock option arrangement approved by the Board (appropriately adjusted for stock splits and combinations) to directors, officers, or employees of, consultants or providers of goods or services to, Company, Borrower or any of their respective Subsidiaries or any other person eligible to acquire Common Stock of Company under said plans or arrangements, (3)

8

upon conversion of shares of the Company’s Series B Participating Preferred Stock, par value $0.01 per share, (4) as non-voting Common Stock issued in exchange for voting Common Stock (or vice versa) on a share for share basis, (5) which has already been deemed issued hereunder and taken into account in the adjustment of the Warrant Price to the extent required by this Section 6, (6) in connection with the issuances of Common Stock pursuant to the exercise of any warrant issued in connection with a public offering or private placement of debt securities in an aggregate principal amount of not less than $25,000,000, and (7) in connection with the issuance of Common Stock pursuant to the exercise of the warrant to purchase 24,969 shares of Common Stock issued to Holder.

(iii) If, at any time during the Adjustment Period, the number of shares of Common Stock outstanding is increased by a stock dividend payable in shares of Common Stock or by a subdivision or split-up of shares of Common Stock, then, following the record date fixed for the determination of holders of Common Stock entitled to receive such stock dividend, subdivision or split-up, the Warrant Price shall be appropriately decreased and the number of shares of Common Stock issuable upon the exercise hereof shall be increased in proportion to such increase in outstanding shares.

(iv) If, at any time during the Adjustment Period, the number of shares of Common Stock outstanding is decreased by a combination of the outstanding shares of Common Stock, then, following the record date for such combination, the Warrant Price shall be appropriately increased and the number of shares of Common Stock issuable upon the exercise hereof shall be decreased in proportion to such decrease in outstanding shares.

(v) In case, at any time during the Adjustment Period, Company shall declare a cash dividend upon its Common Stock payable otherwise than out of earnings or earned surplus or shall distribute to holders of its Common Stock shares of its capital stock (other than Common Stock), stock or other securities of other persons, evidences of indebtedness issued by Company or other persons, assets (excluding cash dividends and distributions) or options or rights (excluding options to purchase and rights to subscribe for Common Stock or other securities of Company convertible into or exchangeable for Common Stock), then, in each such case, immediately following the record date fixed for the determination of the holders of Common Stock entitled to receive such dividend or distribution, the Warrant Price in effect thereafter shall be determined by multiplying the Warrant Price in effect immediately prior to such record date by a fraction of which the numerator shall be an amount equal to the difference of (x) the Current Market Price of one share of Common Stock minus (y) the fair market value (as determined by the Board, whose determination shall be conclusive) of the amount of cash, stock, securities, evidences of indebtedness, assets, options or rights, as the case may be, so distributed in respect of one share of Common Stock, and of which the denominator shall be such Current Market Price.

(vi) All calculations under this Section 6 shall be made to the nearest cent or to the nearest one-tenth (1/10) of a share, as the case may be.

(vii) For the purpose of any computation pursuant to this Section 6, the Current Market Price at any date of one share of Common Stock shall be deemed to be the average of the daily

9

closing prices for the 10 consecutive business days ending on the last business day before the day in question (as adjusted for any stock dividend, split, combination or reclassification that took effect during such 10 business day period). The closing price for each day shall be the last reported sales price regular way or, in case no such reported sales took place on such day, the average of the last reported bid and asked prices regular way, in either case on the principal national securities exchange on which the Common Stock is listed or admitted to trading or as reported by Nasdaq (or if the Common Stock is not at the time listed or admitted for trading on any such exchange or if prices of the Common Stock are not reported by Nasdaq then such price shall be equal to the average of the last reported bid and asked prices on such day as reported by The National Quotation Bureau Incorporated or any similar reputable quotation and reporting service, if such quotation is not reported by The National Quotation Bureau Incorporated); provided, however, that if the Common Stock is not traded in such manner that the quotations referred to in this clause (vii) are available for the period required hereunder, the Current Market Price shall be determined in good faith by the Board or, if such determination cannot be made, by a nationally recognized independent investment banking or accounting firm selected by the Board (or if such selection cannot be made, by a nationally recognized independent investment banking or accounting firm selected by the AAA in accordance with its rules).

(viii) Whenever the Warrant Price shall be adjusted as provided in this Section 6, Company shall prepare a statement showing the facts requiring such adjustment and the Warrant Price that shall be in effect after such adjustment. Company shall cause a copy of such statement to be sent by mail, first class postage prepaid, to each Holder at its, his or her address appearing on Company’s records. Where appropriate, such copy may be given in advance and may be included as part of the notice required to be mailed under the provisions of clause (x) of this Section 6.

(ix) Adjustments made pursuant to clauses (iii), (iv) and (v) above shall be made on the date such dividend, subdivision, split-up, combination or distribution, as the case may be, is made, and shall become effective at the opening of business on the business day next following the record date for the determination of stockholders entitled to such dividend, subdivision, split-up, combination or distribution.

(x) In the event Company shall propose to take any action of the types described in clauses (iii), (iv), or (v) of this Section 6, Company shall forward, at the same time and in the same manner, to Holder such notice, if any, which Company shall give to the holders of capital stock of Company.

(xi) In any case constituting a Sale Trigger Event in which the provisions of this Section 6 shall require that an adjustment shall become effective immediately after a record date for such Sale Trigger Event, Company may defer until the occurrence of such Sale Trigger Event issuing to Holder all or any part of this Warrant which is exercised after such record date the additional shares of capital stock issuable upon such exercise by reason of the adjustment required by such Sale Trigger Event over and above the shares of capital stock issuable upon such exercise before giving effect to such adjustment; provided, however, that Company shall deliver to such Holder a due bill or other appropriate instrument evidencing such Holder’s right to receive such additional shares upon the occurrence of such Sale Trigger Event requiring such adjustment.

10

SECTION 7. Ownership.

7.1 Ownership of This Warrant. Company may deem and treat the person in whose name this Warrant is registered as the holder and owner hereof (notwithstanding any notations of ownership or writing hereon made by anyone other than Company) for all purposes and shall not be affected by any notice to the contrary until presentation of this Warrant for registration of transfer as provided in this Section 7.

7.2 Transfer and Replacement. Subject to the restrictions of Section 7.3 hereof, this Warrant and all rights hereunder are transferable in whole or in part upon the books of Company by Holder hereof in person or by duly authorized attorney, and a new Warrant or Warrants, of the same tenor as this Warrant but registered in the name of the transferee or transferees (and in the name of Holder, if a partial transfer is effected) shall be made and delivered by Company upon surrender of this Warrant duly endorsed, at the office of Company referred to in Section 13 hereof, together with a properly executed Assignment (in the form of Exhibit B or Exhibit C hereto, as the case may be). Upon receipt by Company of evidence reasonably satisfactory to it of the loss, theft or destruction, and, in such case, of indemnity or security reasonably satisfactory to it, and upon surrender of this Warrant if mutilated, Company shall make and deliver a new Warrant of like tenor, in lieu of this Warrant. This Warrant shall be promptly cancelled by Company upon the surrender hereof in connection with any transfer or replacement. Except as otherwise provided above, in the case of the loss, theft or destruction of a Warrant, Company shall pay all expenses, taxes and other charges payable in connection with any transfer or replacement of this Warrant, other than stock transfer taxes (if any) payable in connection with a transfer of this Warrant, which shall be payable by Holder. Holder shall not transfer this Warrant and the rights hereunder except in compliance with federal and state securities laws.

7.3 Restrictions on Transfer. Holder shall not transfer, directly or indirectly, the Warrant or any Warrant Shares owned or controlled by it (i) to any person with substantial operations as a telecommunications service provider, (ii) in amounts of less than 100,000 Warrant Shares in any single transaction (such number shall be adjusted proportionately each time an adjustment is made under Section 5 as to the number of shares subject to this Warrant), or (iii) to any person who is not an “accredited investor” as that term is defined in Regulation D promulgated under the Securities Act.

SECTION 8.

8.1 Mergers, Consolidation, Sales. In the case of any proposed consolidation or merger of Company with another entity, or the proposed sale of all or substantially all of its assets to another person or entity, that does not constitute a Trigger Event or any other proposed reorganization or reclassification of the capital stock of Company, then, as a condition of such consolidation, merger, sale, reorganization or reclassification that does not constitute a Trigger Event, Company shall give 30 days’ prior written notice thereof to Holder hereof and lawful and adequate provision shall be made whereby Holder shall thereafter have the right to receive upon

11

the basis and upon the terms and conditions specified herein, in lieu of the shares of the Common Stock of Company immediately theretofore purchasable hereunder, such shares of stock, securities or assets as may (by virtue of such consolidation, merger, sale, reorganization or reclassification) be issued or payable with respect to or in exchange for the number of shares of such Common Stock purchasable hereunder immediately before such consolidation, merger, sale, reorganization or reclassification. In any such case appropriate provision shall be made with respect to the rights and interests of Holder to the end that the provisions hereof shall thereafter be applicable as nearly as may be practicable, in relation to any shares of stock, securities or assets thereafter deliverable upon the exercise of this Warrant.

8.2 Approved Sale.

(i) Notwithstanding the foregoing, in the event that the Board votes for and consents to a Sale Trigger Event (an “Approved Sale”) Holder (which term when used in this Section 8.2 shall include Holder’s successors, assigns and transferees) shall vote for (to the extent Holder has voting rights), consent to and raise no objections against such Approved Sale. If the Approved Sale is structured (A) as a merger or consolidation, Holder shall waive any dissenters rights, appraisal rights or similar rights in connection with such merger or consolidation and agree to accept in exchange for the Warrant, the consideration the Holder would have received had the Warrant been exercised for shares of Common Stock prior to such merger or consolidation, or (B) as a sale of securities, Holder shall agree to sell all of Holder’s Warrants, Warrant Shares and other securities of Company held by Holder on the terms and conditions of the Approved Sale. Holder shall take all necessary or desirable actions in connection with the consummation of the Approved Sale as reasonably requested by the Board.

(ii) The obligations of Holder with respect to an Approved Sale are subject to the satisfaction of the following conditions: (A) upon the consummation of the Approved Sale, Holder shall, without duplication, receive in consideration of the shares of Common Stock then held by Holder (including shares acquired by Holder upon exercise of its Warrants in connection with such Approved Sale), the same per share consideration that is received by other holders of Common Stock in consideration of their shares of Common Stock that are sold in or voted in favor of such Approved Sale, and (B) if the holders of Common Stock and/or Class B Preferred Stock (or equity securities exchangeable therefor) are given an option as to the form and consideration to be received, Holder shall be given the same option.

SECTION 9. Notice of Dissolution or Liquidation. In case of any distribution of the assets of Company in dissolution or liquidation (except under circumstances when the foregoing Section 8 shall be applicable), Company shall give notice thereof to Holder hereof and shall make no distribution to shareholders until the expiration of ten (10) days from the date of mailing of the aforesaid notice and, in any case, Holder hereof may exercise this Warrant within thirty (30) days from the date of the giving of such notice, and all rights herein granted not so exercised within such thirty-day period shall thereafter become null and void. Such distribution of the assets of Company shall, for purposes of this Section 9, be deemed a Sale Trigger Event and the date of such notice shall, for purposes of this Section 9, be deemed the date of a Sale Trigger Event.

12

SECTION 10. Fractional Shares. Fractional shares shall not be issued upon the exercise of this Warrant but in any case where Holder would, except for the provisions of this Section 10, be entitled under the terms hereof to receive a fractional share upon the complete exercise of this Warrant, Company shall, upon the exercise of this Warrant for the largest number of whole shares then called for, pay a sum in cash equal to the excess of the value of such fractional share (determined in such reasonable manner as may be prescribed in good faith by the Board) over the Warrant Price for such fractional share.

SECTION 11. Special Arrangements of Company. Company covenants and agrees that during the Adjustment Period, unless otherwise approved by Holder:

11.1 Shall Not Amend Certificate. Company shall not amend its certificate or articles, as the case may be, of incorporation to eliminate as an authorized class of capital stock that class denominated as “Common Stock” on the date hereof.

11.2 Shall Bind Successors. This Warrant shall be binding upon any corporation or other person or entity succeeding to Company by merger or consolidation.

SECTION 12. Registration. Company covenants and agrees that the Holder shall be offered the right to become a party to the Registration Rights Agreement.

SECTION 13. Notices. Any notice or other document required or permitted to be given or delivered to Holder shall be delivered at, or sent by certified or registered mail to, Holder at its address for notices set forth in the Agreement or to such other address as shall have been furnished to Company in writing by Holder. Any notice or other document required or permitted to be given or delivered to Company shall be delivered at, or sent by certified or registered mail to, Company at its address for notices set forth in the Agreement or to such other address as shall have been furnished in writing to Holder by Company. Any notice so addressed and mailed by registered or certified mail shall be deemed to be given when so mailed. Any notice so addressed and otherwise delivered shall be deemed to be given when actually received by the addressee.

SECTION 14. No Rights as Stockholder; Limitation of Liability. This Warrant shall not entitle Holder to any of the rights of a shareholder of Company except upon exercise in accordance with the terms hereof. No provision hereof, in the absence of affirmative action by Holder to purchase shares of Common Stock, and no mere enumeration herein of the rights or privileges of Holder, shall give rise to any liability of Holder for the Warrant Price hereunder or as a shareholder of Company, whether such liability is asserted by Company or by creditors of Company.

SECTION 15. Law Governing. THE VALIDITY, INTERPRETATION, AND ENFORCEMENT OF THIS WARRANT SHALL BE GOVERNED BY AND CONSTRUED IN ACCORDANCE WITH THE LAWS OF THE STATE OF DELAWARE WITHOUT GIVING EFFECT TO THE CONFLICT OF LAW PRINCIPLES THEREOF.

SECTION 16. Amendments. This Warrant and any provision hereof may be changed, waived, discharged or terminated only by an instrument in writing signed by both parties (or any respective predecessor in interest thereof). The headings in this Warrant are for purposes of reference only and shall not affect the meaning or construction of any of the provisions hereof.’

13

IN WITNESS WHEREOF, Company has caused this Warrant to be signed by its duly authorized officer this 31st day of March, 2004.

Agreed and Accepted

14

EXHIBIT A

FORM OF NOTICE OF EXERCISE

[To be signed only upon exercise of the Warrant]

TO BE EXECUTED BY THE REGISTERED HOLDER

TO EXERCISE THE ATTACHED WARRANT

The undersigned hereby exercises the right to purchase                      shares of Common Stock which the undersigned is entitled to purchase by the terms of the attached Warrant according to the conditions thereof, herewith directs Company to issue                      shares, and either (i) directing the Company to withhold                      shares in lieu of payment of the Warrant Price, as described in Section 2.1 of the Warrant or (ii) enclosing payment of the Warrant Price for such shares].

All shares to be issued pursuant hereto (i) shall be issued only following the making of usual and customary investment representations appropriate under the circumstances and (ii) shall be issued in the name of and the initial address of such person to be entered on the books of Cbeyond Communications, Inc. shall be:

The shares are to be issued in certificates of the following denominations:

Dated:                     

EXHIBIT B

FORM OF ASSIGNMENT

(ENTIRE)

[To be signed only upon transfer of entire Warrant]

TO BE EXECUTED BY THE REGISTERED HOLDER

TO TRANSFER THE ATTACHED WARRANT

FOR VALUE RECEIVED                                      hereby sells, assigns and transfers unto                                                           all rights of the undersigned under and pursuant to the attached Warrant, and the undersigned does hereby irrevocably constitute and appoint                                      Attorney to transfer said Warrant on the books of Cbeyond Communications, Inc., with full power of substitution.

Dated:                     

NOTICE

The signature to the foregoing Assignment must correspond to the name as written upon the face of the attached Warrant in every particular, without alteration or enlargement or any change whatsoever.

EXHIBIT C

FORM OF ASSIGNMENT

(PARTIAL)

[To be signed only upon partial transfer of Warrant]

TO BE EXECUTED BY THE REGISTERED HOLDER

TO TRANSFER THE ATTACHED WARRANT

FOR VALUE RECEIVED                                                   hereby sells, assigns and transfers unto                                                           (i) the rights of the undersigned to purchase                      shares of Common Stock under and pursuant to the attached Warrant, and (ii) on a non-exclusive basis, all other rights of the undersigned under and pursuant to the attached Warrant, it being understood that the undersigned shall retain, severally (and not jointly) with the transferee(s) named herein, all rights assigned on such non-exclusive basis. The undersigned does hereby irrevocably constitute and appoint                                                           Attorney to transfer said Warrant on the books of Cbeyond Communications, Inc., with full power of substitution.

Dated:                     

NOTICE

The signature to the foregoing Assignment must correspond to the name as written upon the face of the attached Warrant in every particular, without alteration or enlargement or any change whatsoever.