AMENDMENT TO ESCROW AGREEMENT

Exhibit 10.12

AMENDMENT TO ESCROW AGREEMENT

This Amendment to Escrow Agreement is entered into pursuant to paragraph 17 of that certain Escrow Agreement made and entered into the 28th day of September, 1999, by and among MADISON RIVER TELEPHONE COMPANY, LLC, a Delaware limited liability company (“MRTC”), GULF MERGER CORPORATION, an Alabama corporation (“GMC”), GULF COAST SERVICES, INC., an Alabama corporation (“GCSI”), the former owners of all of the issued and outstanding capital stock of GCSI as of the date of the Escrow Agreement (such former owners, or their successors in interest, hereafter referred to as the “GCSI Stockholders”) and REGIONS BANK, an Alabama banking corporation “Escrow Agent”).

MRTC, GCSI (as itself and as successor in interest to GMC), the GCSI Stockholders and the Escrow Agent, with the consent of the RURAL TELEPHONE FINANCE COOPERATIVE (“RTFC”) hereby amend paragraphs 6 and 10 of the Escrow Agreement by striking them in their entirety and replacing them with paragraphs 6 and 10 as set forth below. This Amendment to the Escrow Agreement may be executed in one or more counterparts, each of which will be deemed to be an original but all of which together, will constitute one and the same instrument.

6. Escrow Fund. The Parties agree that the Escrow Fund shall be held and treated by Escrow Agent under the following terms and conditions:

(a) Through a disbursement notice signed only by Paul H. Sunu of MRTC, or such other person designated in writing by MRTC to Escrow Agent from time to time, MRTC may draw upon the Escrow Fund to pay expenses (including, but not limited to, attorneys’ fees but excluding any allocation of costs of MRTC or GCSI salary or general overhead expenses) incurred by MRTC, GCSI or any of their subsidiaries or affiliates, in connection with investigating, defending, settling or prosecuting any action, suit, proceeding, declaratory judgment action, claim, counterclaim, dispute or litigation (other than claims covered under the workers compensation laws of the State of Alabama) (individually or collectively, “Proceedings”) which:

(1) as of the date of the original September 28, 1999 Escrow Agreement have a court docket number; or

(2) (i) arise from, or are related to, claims, counterclaims, crossclaims or circumstances referenced in any Proceedings described in (1) above, and (ii) which are filed on behalf of any current or future claimant in such Proceedings described in (1) above or any similarly situated claimant in any future Proceedings. The claims referenced in this paragraph 6(a) (2) shall be deemed to include, but not be limited to, any Proceedings arising out of any present or former employee’s interests in the Gulf Telephone Company Restated Employee Stock Ownership Plan and/or 401(k) Plan.

MRTC shall give the Escrow Committee advance notice of at least fifteen (15) business days prior to any such payments, along with copies of supporting invoices. The Escrow Committee shall have the right to object to any payment which it decides is not a bona fide payment to a third party, and shall have the right to obtain reimbursement of such payments either from the party to whom payment was made or the party on whose behalf payment was made. In addition, MRTC may draw upon the Escrow Fund to pay insurance premiums for a sixty-month, $10,000,000 supplemental directors and officer liability policy. It is the understanding of the Parties that such policy will not cover any matter related to a Proceeding.

(b) The Escrow Fund may also be drawn upon to pay any or all of the following amounts, through a disbursement notice signed by a majority of all members of the Escrow Committee:

(1) any deficiency in the Minimum Cash Amount as determined by the Final Closing Date Financial Statements;

(2) unpaid obligations of GCSI (or amounts required to settle any such matters) set forth in subsections 5.1(b)(i), (ii) and (iii) of the Merger Agreement, as determined by the Final Closing Date Financial Statements; and

(3) amounts constituting or satisfying any and all actions, suits, proceedings, claims, liabilities, demands, settlements, assessments, judgments, interest, penalties, costs and expenses, including reasonable attorneys’ fees (whether or not incurred in connection with investigating, defending, settling or prosecuting any action, suit, proceeding or claim against MRTC, GCSI, the ESOP, or any affiliate, officer, director or employee thereof hereunder), incident to any Proceedings referred to in paragraph (a) of this Section 6.

(c) In its sole discretion, and through a disbursement notice signed only by MRTC, MRTC may, upon confirmation of irrevocable insurance coverage, without reservation, instruct Paying Agent to release an amount equal to the directors and officers insurance coverage in place and available to satisfy any amounts payable under each of the provisions of this Section 6.

(d) The Escrow Fund shall, upon notice to the Escrow Agent by MRTC, be drawn upon to satisfy any final non-appealable judgment, plus post judgment interest if applicable, against MRTC, GCSI, the ESOP, or any of their affiliates, officers, directors, or trustees, or employees in any Proceedings referred to in paragraph (a) of this Section 6.

(e) After (and not before) the later of: (i) a final, non-appealable resolution of all Proceedings or Related Proceedings referred to in paragraph (a) of this Section 6 filed within six (6) years of the date of this Amendment; (ii) a final non-appealable resolution of all claims arising from claims or circumstances described in any

2

Proceedings which as of this date have a court docket number and which is binding, as a matter of law, on all Claimants; or (iii) six (6) years, in the event that no claims described in (e)(ii) above are filed within such six (6) year period; and upon finalization and payment of all matters to be determined under paragraph (a) of this Section 6, the Escrow Committee shall cause the Escrow Agent to disburse the remainder of the Escrow Fund. Upon receipt of a disbursement notice signed by all members of the Escrow Committee, the Escrow Agent shall pay to MRTC any amounts due under this Agreement, and thereafter, to each GCSI Stockholder that has previously surrendered, or subsequently surrenders, such certificate(s) (other than certificates representing Dissenting Shares) a pro rata share, with such adjustments as may be necessary as a result of individual payments by certain stockholders, which payments were applied to GCSI’s outstanding indebtedness with CoBank, as established by such documentation as may be requested by the Escrow Committee, (based on the number of issued and outstanding GCSI Shares immediately prior to the Effective Time) of the remaining Escrow Fund for each GCSI Share represented by the surrendered certificate(s), which amount shall be paid by Escrow Agent within five (5) business days of receipt of the disbursement notice. The disbursement notice shall specify any and all amounts to be paid and the recipients of the amounts specified in such notice.

(f) For amounts referenced in paragraphs (b)(1) and (2) of this Section 6, such amounts must exceed a threshold of $25,000.00 per item and such amounts may not exceed $2,000,000 in the aggregate.

10. Notices. All notices, requests, demands, claims and other communications under this Agreement will be in writing. Any notice, request, demand, claim or other communication hereunder shall be deemed duly given upon personal delivery to the intended recipient, or if (and then two (2) business days after) it is sent by registered or certified mail, return receipt requested, postage prepaid, and addressed to the intended recipient as set forth below:

If to MRTC, GMC or GCSI:

Madison River Telephone Company, LLC

103 South Fifth Street

Mebane, North Carolina 27302

Attention: Paul H. Sunu

(919) 563-1500

(919) 563-4993 fax

***@***

With a copy to:

Matt L. Springer

Vice President and General Counsel

Madison River Communications, Inc.

103 South Fifth Street

Mebane, North Carolina 27302

(919) 563-1500

(919) 563-4993 fax

***@***

3

Larry E. Robbins, Esq.

Wyrick, Robbins, Yates & Ponton, LLP

Suite 300

4101 Lake Boone Trail

Raleigh, North Carolina 27607

(919) 781-4000

(919) 781-4865 fax

***@*** e-mail

If to the GCSI Stockholders:

Marjorie Y. Snook, as a Trustee of the John McClure Snook Testamentary Trust

c/o M. Mort Swaim, Esq.

235 West Laurel Avenue

Foley, Alabama 36535

(334) 943-3999

(334) 943-3137 fax

***@*** e-mail

Regions Bank, as Trustee of John McClure Snook Testamentary Trust

Trust Department

104 St. Francis Street, 2nd Floor

P.O. Box 2527

Mobile, Alabama 36602

Attention: Robert B. Doyle

(334) 690-1452

(334) 690-1591 fax

***@*** e-mail

With a copy to:

GCSI Stockholders as set forth on Exhibit “A” hereto

R. Gregory Watts

Johnstone, Adams, Bailey, Gordon & Harris, L.L.C.

Royal St. Francis Building

104 St. Francis Street

Mobile, Alabama 36602

(334) 432-7682

(334) 432-2800 fax

***@*** e-mail

4

John Hommel and North Star ESOP & Fiduciary Services, LLC, as Trustee

of the Gulf Telephone Company

Employee Stock Ownership Plan

500 West Madison Street, Suite 3800

Chicago, Illinois 60661

(312) 559-9761

(312) 559-9762 fax

***@***

With a copy to:

William H. Wasden, Esq.

Pierce, Ledyard, Lata & Wasden P.C.

Suite 500

41 North Beltline Highway

P.O. Box 16046

Mobile, Alabama 36616

(334) 344-5151

(334) 344-9696 fax

***@*** e-mail

If to RTFC:

Rural Telephone Finance Cooperative

Woodland Park

2201 Cooperative Way

Herndon, Virginia 20171-3025

Attention: Loan Officer

(703) 709-6780 fax

If to Escrow Agent:

Regions Bank

Trust Department

104 St. Francis Street, 2nd Floor

P.O. Box 2527

Mobile, Alabama 36602

Attention: Robert B. Doyle

(334) 690-1452

(334) 690-1591 fax

***@*** e-mail

5

With a copy to:

R. Gregory Watts

Johnstone, Adams, Bailey, Gordon & Harris, L.L.C.

Royal St. Francis Building

104 St. Francis Street

Mobile, Alabama 36602

(334) 432-7682

(334) 432-2800 fax

***@*** e-mail

[THE NEXT PAGE IS THE SIGNATURE PAGE]

6

IN WITNESS WHEREOF, the Parties have executed and delivered this Amendment to the Escrow Agreement on the      day of             , 2000.

EXHIBIT A

Dennis Leonard Kaiser

8967 Escambia Avenue

Alberta, Alabama 36530

(334) 961-7566

Harold Killian

501 Cotton Creek Drive

Gulf Shores, Alabama 36542

(334) 955-1600

Robert Howard Younce

2370 Younce Lane

Gulf Shores, Alabama 36542

(334) 968-6431

Robert L. Mackey, Jr.

8660 Winford Lane

East Mobile, Alabama 36619

(334) 633-7417

Ann L. Byrd

Post Office Box 422

Foley, Alabama 36536

(334) 979-8545

Esther Holman Williams

10401 Vernant Park Road

Foley, Alabama 36535

(334) 965-7716

Willard Richard Mitchem

13280 J.B. Williams Road

Loxley, Alabama 36551

(334) 964-5664

Woodard S. Setter

9370 Fairway Drive

Foley, Alabama 36535

(334) 955-1008

Dale Eugene Younce.

15801 George Younce Road

Foley, Alabama 36535

(334) 943-9977