REGISTRATION RIGHTS AGREEMENT

EXHIBIT 4.1

REGISTRATION RIGHTS AGREEMENT

AGREEMENT between FiberNet Telecom Group, Inc., a Delaware corporation (the “Company”), and gateway.realty.new jersey.llc, a New Jersey limited liability company (the “Shareholder”).

W I T N E S S E T H:

WHEREAS, the Company, through its wholly owned subsidiary, Local Fiber, LLC (“Local Fiber”), has purchased substantially all of the assets of the Shareholder pursuant to an Asset Purchase Agreement, dated as of December 31, 2003, between the Company, Local Fiber and the Shareholder (the “Purchase Agreement”); and

WHEREAS, in connection with the Purchase Agreement, the Company intends to register and the Shareholder desires that the Company register the Shares and the Additional Shares, and any other shares of the Company’s Common Stock issued in respect of the Shares or the Additional Shares by way of stock split, stock dividend or other distribution, recapitalization or otherwise, held or to be held by Shareholder or permitted transferees of the Shareholder in such registration (the “Registrable Securities”).

NOW THEREFORE, in consideration of the premises and the mutual terms and provisions hereof, the parties hereto hereby agree as follows:

1. Definitions. For purposes of this Agreement, capitalized terms not otherwise defined herein shall have the meanings set forth in the Purchase Agreement and the following terms shall have the following respective meanings:

(a) “Act” shall mean the Securities Act of 1933, as amended, or any similar federal statute enacted hereafter, and the rules and regulations of the Commission thereunder, all as the same shall be in effect from time to time.

(b) “Commission” shall mean the Securities and Exchange Commission or any other federal agency at the time administering the Act.

(c) “Common Stock” shall mean the common stock, par value $0.001 per share, of the Company.

(d) “Exchange Act” shall mean the Securities Exchange of 1934, as amended, or any similar federal statute enacted hereafter, and the rules and regulations of the Commission thereunder, all as the same shall be in effect from time to time.

(e) “Holder” shall mean the Shareholder and any member of the Shareholder who is the beneficial owner of any of the Shares or the Additional Shares.

(f) “Registrable Securities” shall have the meaning set forth in the second WHEREAS clause hereof

(g) The terms “register,” “registered” and “registration” refer to a registration effected by preparing and filing a registration statement in compliance with the Act and the declaration or ordering of effectiveness of such registration statement by the Commission.

2. Registration.

(a) With respect to the Registrable Securities issued pursuant to Section 3.2(b) of the Purchase Agreement, within thirty (30) days of the date hereof (the “Filing Date”), the Company shall use its commercially reasonable efforts to prepare and file with the Commission a “resale” registration statement covering all such Registrable Securities for an offering to be made on a continuous basis pursuant to Rule 415 under the Act. Such registration statement shall be on Form S-3 (except if the Company is not then eligible to register for resale such Registrable Securities on Form S-3, in which case such registration shall be on another appropriate form in accordance herewith). The Company shall also use its commercially reasonable efforts to have such registration statement declared effective within 60 days from the Filing Date. In the event any shares of Company Common tock are issued in respect of the Shares by way of stock split, dividend or other distribution, recapitalization or otherwise, the Company shall promptly amend the registration to include such newly issued shares to the extent such amendment is necessary to include such issued shares in such registration statement.

(b) With respect to the Registrable Securities issued pursuant to Section 3.3(d) or Section 3.3(e) of the Purchase Agreement, if any, within thirty (30) days of the date of issuance of such Registrable Securities (the “Second Filing Date”), the Company shall use its commercially reasonable efforts to prepare and file with the Commission a “resale” registration statement covering all such Registrable Securities for an offering to be made on a continuous basis pursuant to Rule 415 under the Act. Such registration statement shall be on Form S-3 (except if the Company is not then eligible to register for resale such Registrable Securities on Form S-3, in which case such registration shall be on another appropriate form in accordance herewith). The Company shall also use its commercially reasonable efforts to have the registration statement declared effective within 60 days from the Second Filing Date. In the event any shares of Company Common tock are issued in respect of the Additional Shares by way of stock split, dividend or other distribution, recapitalization or otherwise, the Company shall promptly amend the registration to include such newly issued shares to the extent such amendment is necessary to include such issued shares in such registration statement.

(c) Shareholder acknowledges and understands that: (i) the Company shall register only the Registrable Securities in fulfillment of its obligations to register the Registrable Securities pursuant to the Purchase Agreement; and (ii) the Company shall be under no additional obligation to register any other securities of the Company held by any Holder, including, without limitation, options or other rights of the Shareholder to acquire securities of the Company.

2

3. Furnishing of Information. Each Holder shall furnish to the Company such information regarding the Holder, its officers, directors, shareholders, members, family members, and affiliates, as applicable, the Shares, the Additional Shares and the intended method of disposition of the Registrable Securities as the Company shall reasonably request and as shall be required in connection with the action to be taken by the Company pursuant to this Agreement.

4. Suspension of Disposition of Shares. The Holder agrees that, upon receipt of any notice from the Company, of (a) the happening of any event as a result of which the prospectus included in such registration statement contains an untrue statement of a material fact or omits any fact necessary to make the statements therein not misleading, (b) any requests by the Commission for amendments or supplements to the registration statement or the prospectus or for additional information, (c) the issuance of any stop order suspending the effectiveness of the registration statement, (d) the information in the registration statement no longer being sufficient to permit continued sales under the registration statement, or (e) the receipt by the Company of any notification with respect to the suspension of the qualification of the Registrable Securities for sale in any jurisdiction, the Holder will forthwith discontinue disposition of the Registrable Securities until the Company notifies the Holder in writing that sales of Registrable Securities may continue. If so directed by the Company, such Holder will deliver to the Company (at the expense of the Company) all copies, other than permanent file copies then in the Holder’s possession, of the prospectus covering such Registrable Securities at the time of receipt of such notice.

5. Expenses of Registration. All reasonable expenses, other than underwriting discounts and commissions, incurred in connection with registrations, filings or qualifications pursuant to Section 2, including, without limitation, all registration, listing and qualification fees, printers and accounting fees and the fees and disbursements of counsel for the Company and one counsel for the Holders shall be borne by the Company; provided, however, that in no event shall the Company be responsible for more than $7,500 in fees and disbursements of such counsel in any registration hereunder. The Shareholder shall bear the fees and disbursements of its own counsel, if any, in excess of those referred to in the immediately preceding sentence, which fees of such counsel shall not exceed $7,500.

6. Limitation of the Company’s Obligations. The Company shall not be obligated under this Agreement to register or include in any registration Registrable Securities that any Holder has requested to be registered if the Company shall furnish such Holder with a written opinion of counsel reasonably acceptable to the Holder that all Registrable Securities that such Holder holds may be publicly offered, sold and distributed without registration under the Act pursuant to Rule 144 promulgated by the Commission under the Act without restriction as to the amount of securities that can be sold or the timing of any such sale.

7. Indemnification.

(a) Except in the case of a sale by a Holder in violation of Section 4 hereof, the Company agrees to indemnify and hold harmless each Holder, its directors, its members, its officers and each person, if any, who controls any Holder within the meaning of Section 15 of the

3

Act or Section 20 of the Exchange Act, from and against any and all losses, claims, damages, liabilities and judgments (including, without limitation, any reasonable legal or other expenses incurred in connection with investigating or defending any matter, including any action, that could give rise to any such losses, claims, damages, liabilities or judgments) caused by any untrue statement of a material fact contained in the registration statement filed by the Company pursuant to Section 2, including any final prospectus contained therein (or any amendment thereto), or caused by any omission or alleged omission to state therein a material fact required to be stated therein or necessary to make the statements therein not misleading, except insofar as such losses, claims, damages, liabilities or judgments are caused by any such untrue statement or omission or alleged untrue statement or omission based upon information relating to any Holder furnished in writing to the Company by such Holder expressly for use therein.

(b) Each Holder agrees to indemnify and hold harmless the Company, its directors, its officers and each person, if any, who controls the Company within the meaning of Section 15 of the Act or Section 20 of the Exchange Act, from and against any and all losses, claims, damages, liabilities and judgments (including, without limitation, any legal or other expenses incurred in connection with investigating or defending any matter, including any action, that could give rise to any such losses, claims, damages, liabilities or judgments) caused by any untrue statement of a material fact contained in the registration statement filed pursuant to Section 2, including any final prospectus contained therein (or any amendment thereto), or caused by any omission or alleged omission to state therein a material fact required to be stated therein or necessary to make the statements therein not misleading, but only with respect to losses, claims, damages, liabilities and judgments caused by an untrue statement or omission or alleged untrue statement or omission based on information relating to such Holder furnished in writing by or on behalf of such Holder expressly for use in the registration statement filed pursuant to Section 2, including any final prospectus contained therein (or any amendment thereto).

(c) In case any action shall be commenced involving any person entitled to indemnification pursuant to Section 7(a) or 7(b) (the “Indemnified Party”), the Indemnified Party shall promptly notify the person against whom such indemnity may be sought (the “Indemnifying Party”) in writing and the Indemnifying Party shall assume the defense of such action, including the employment of counsel reasonably satisfactory to the Indemnified Party and the payment of all reasonable fees and expenses of such counsel, as incurred. Any Indemnified Party shall have the right to employ separate counsel in any such action and participate in the defense thereof, but the fees and expenses of such counsel shall be at the expense of the Indemnified Party unless (i) the employment of such counsel shall have been specifically authorized in writing by the Indemnifying Party, (ii) the Indemnifying Party shall have failed to assume the defense of such action or employ counsel reasonably satisfactory to the Indemnified Party or (iii) the named parties to any such action (including any impleaded parties) include both the Indemnified Party and the Indemnifying Party, and the Indemnified Party shall have been advised by such counsel that there may be one or more legal defenses available to it which are different from or additional to those available to the Indemnifying Party (in which case the Indemnifying Party shall not have the right to assume the defense of such action on behalf of the Indemnified Party). In any such case, the Indemnifying Party shall not, in connection with any one action or separate but

4

substantially similar or related actions in the same jurisdiction arising out of the same general allegations or circumstances, be liable for the reasonable fees and expenses of more than one separate firm of attorneys (in addition to any local counsel) for all Indemnified Parties. The Indemnifying Party shall indemnify and hold harmless the Indemnified Party from and against any and all losses, claims, damages, liabilities and judgments by reason of any settlement of any action effected with its written consent. No Indemnifying Party shall, without the prior written consent of the Indemnified Party, effect any settlement or compromise of, or consent to the entry of judgment with respect to, any pending or threatened action in respect of which the Indemnified Party is or could have been a party and indemnity or contribution may be or could have been sought hereunder by the Indemnified Party, unless such settlement, compromise or judgment (i) includes an unconditional release of the Indemnified Party from all liability on claims that are or could have been the subject matter of such action, (ii) does not include a statement as to or an admission of fault, culpability or a failure to act, by or on behalf of the Indemnified Party and (iii) involves only the payment of money by the Indemnified Party.

(d) To the extent the indemnification provided for in this Section 7 is unavailable (other than in accordance with the terms hereof) to an Indemnified Party or insufficient in respect of any losses, claims, damages, liabilities or judgments referred to therein, then each Indemnifying Party, in lieu of indemnifying such Indemnified Party, shall contribute to the amount paid or payable by such Indemnified Party as a result of such losses, claims, damages, liabilities and judgments (i) in such proportion as is appropriate to reflect the relative benefits received by the Indemnifying Party(ies) on the one hand and the Indemnified Party(ies) on the other hand from the offering of the Shares or Additional Shares, as the case may be, or (ii) if the allocation provided by clause 7(d)(i) above is not permitted by applicable law, in such proportion as is appropriate to reflect not only the relative benefits referred to in clause 7(d)(i) above but also the relative fault of the Indemnifying Party or parties on the one hand and the Indemnified Party or parties on the other hand in connection with the statements or omissions which resulted in such losses, claims, damages, liabilities or judgments, as well as any other relevant equitable considerations; provided, however, that in no event shall any Holder be liable for any amounts in excess of the proceeds from the sale of such Holder’s Shares and Additional Shares hereunder. The relative fault of the Company and the Holder shall be determined by reference to, among other things, whether the untrue or alleged untrue statement of a material fact or the omission or alleged omission to state a material fact relates to information supplied by the Company or the Holder, and the parties’ relative intent, knowledge, access to information and opportunity to correct or prevent such statement or omission. The amount paid or payable by an Indemnified Party as a result of the losses, claims, damages, liabilities or judgments referred to in the immediately preceding paragraph shall be deemed to include, subject to the limitations set forth above, any reasonable legal or other expenses incurred by such Indemnified Party in connection with investigating or defending any matter, including any action, that could have given rise to such losses, claims, damages, liabilities or judgments. No person guilty of fraudulent misrepresentation (within the meaning of Section 11(f) of the Act) shall be entitled to contribution from any person who was not guilty of such fraudulent misrepresentation.

8. Agreements of the Holders. Each Holder agrees:

5

(a) whether or not the transactions contemplated in this Agreement are consummated or this Agreement is terminated, to pay or cause to be paid all reasonable expenses incident to the performance of the Holder’s obligations under this Agreement, including: (i) any fees, disbursements and expenses of Holder’s counsel in connection with the registration and delivery of the Registrable Securities under the Act as required by Section 5 of this Agreement, (ii) all costs and expenses related to the transfer and delivery of the Registrable Securities, including any transfer or other taxes payable thereon, and (iii) all other costs and expenses incident to the performance of the obligations of the Holder hereunder for which provision is not otherwise made in this Agreement. The provisions of this Section shall not supersede or otherwise affect any separate agreement that the Company and any Holder or Holders may have for allocation of such expenses among themselves; and

(b) that such Holder will not offer to sell, contract to sell, or otherwise sell, dispose of, loan, pledge or grant any rights with respect to (collectively, a “Disposition”) the Shares or any other securities of the Company issued in respect of the Shares (by way of stock split, stock dividend or other distribution, recapitalization or otherwise) (collectively, “Securities”) now owned or hereafter acquired directly or indirectly by such person or with respect to which such person has or hereafter acquires the power of Disposition, otherwise than (i) as a bona fide gift or gifts, provided the donee or donees thereof agree in writing to be bound by this restriction, (ii) as a distribution to members of such person, provided that the distributees thereof agree in writing to be bound by the terms of this restriction, or (iii) with the prior written consent of the Company. The foregoing restrictions shall commence on the date hereof and end, subject to applicable federal and state securities laws, on the earlier of (x) the 180^th day following the date the registration statement as required to be filed pursuant to Section 2(a) herein is declared effective by the Commission (the “Lock-Up Period”), and (y) September 30, 2004. The Holder agrees that the foregoing restriction precludes the Holder from engaging in any hedging or other transaction that is designed to or reasonably expected to lead to or result in a Disposition of Securities during the Lock-up Period, even if such Securities would be disposed of by someone other than such Holder. Such prohibited hedging or other transactions would include, without limitation, any short sale (whether or not against the box) or any purchase, sale or grant of any right (including, without limitation, any put or call option) with respect to any Securities or with respect to any security (other than a broad-based market basket or index) that includes, relates to or derives any significant part of its value from Securities. The Holder also agrees and consents to the entry of stop transfer instructions with the Company’s transfer agent and registrar against the transfer of Securities held by such Holder except in compliance with the foregoing restrictions.

9. Amendments and Waivers. The provisions of this Agreement, including the provisions of this sentence, may be amended, modified or supplemented, and waivers or consents to departures from the provisions hereof may be given, by written consent of the Company and the Shareholder.

6

10. Notices. All notices and other communications hereunder shall be in writing by (i) delivery by hand, (ii) facsimile transmission (provided that such materials shall also be sent via recognized overnight courier on the date such facsimile is sent), (iii) recognized overnight courier, or (iv) certified mail, return receipt requested, postage prepaid:

(a) if to a Holder, at the most current address given by such Holder to the Company in accordance with the provisions of this Section 10, which address initially shall be the address given to the Company upon acquisition of the Shares unless the Holder has notified the Company of a change of address; and

(b) if to the Company, initially at its address set forth below and thereafter at such other address, notice of which is given in accordance with the provisions of this Section 10:

All notices and other communications hereunder shall be deemed to have been (a) if by hand, at the time of the delivery thereof to the receiving party at the address of such party set forth above, (b) if sent by facsimile transmission, at the time receipt has been acknowledged by electronic confirmation or otherwise, (c) if sent by overnight courier, on the next business day following the day such notice is delivered to the courier service, or (d) if sent by certified mail, on the fifth business day following the day such mailing is made.

11. Counterparts. This Agreement may be executed in two or more counterparts, each of which when so executed shall be deemed to be an original and all of which taken together shall constitute one and the same agreement.

12. Headings. The headings in this Agreement are for convenience of reference only and shall not limit or otherwise affect the meaning hereof.

13. Governing Law. This Agreement shall be governed by and construed in accordance with the laws of the State of New York.

14. Severability. In the event that any one or more of the provisions contained herein, or the application thereof in any circumstance, is held invalid, illegal or unenforceable, the validity, legality and enforceability of any such provision in every other respect and of the remaining provisions contained herein shall not be affected or impaired thereby.

15. Entire Agreement. This Agreement, in conjunction with the Purchase Agreement, is intended by the parties as a final expression of their agreement and intended to be a complete and exclusive statement of the agreement and understanding of the parties hereto in respect of the subject matter contained herein. There are no restrictions, promises, warranties or undertakings, other than those set forth or referred to herein with respect to the registration rights granted by the

7

Company with respect to the Registrable Securities. This Agreement supersedes all prior agreements and understandings between the parties with respect to registration of the Registrable Securities. Nothing in this Agreement shall preclude the Company from entering into any other agreement having the same or different terms with any holder of the Company’s securities or any third party with respect to registration rights or related matters.

16. Assignment. The rights of the Shareholder under this Agreement may be assigned by the Shareholder to any or all of the members of the Shareholder upon any sale, distribution or other disposition of Shares or Additional Shares to any such member, provided that in connection with such assignment such member agrees in a writing reasonably acceptable to the Company to be bound by the terms and conditions of this Agreement. Each such assignee shall be deemed to be a Holder for purposes of this Agreement.

17. Parties Benefited. Except as set forth in Section 16 hereof, nothing in this Agreement, express or implied, is intended to confer upon any third party any rights, remedies, obligations or liabilities.

IN WITNESS WHEREOF, the parties have executed this Agreement as of January 30, 2004.

8