<PAGE>

                                                                  EXHIBIT 10.1.3

                            SHAREHOLDERS AGREEMENT
                         COASTAL COMMUNICATIONS, INC.


          THIS SHAREHOLDERS AGREEMENT is made and entered into effective this
30th day of March, 2000, by and among Coastal Communications, Inc., a Delaware
corporation (the "Company"), and the persons indicated on Exhibit A hereto
                  -------                                 ---------
(individually a "Shareholder" and collectively the "Shareholders").
                 -----------                        ------------

                                   RECITALS
                                   --------

          WHEREAS, the Shareholders are collectively the owners of all the
issued and outstanding capital stock of the Company; and

          WHEREAS, the Company and the Shareholders wish to set forth the terms
and conditions under which the Series A and Series B Shareholders may sell to
the Company and the Company may purchase their Stock; and

          WHEREAS, the Company and the Shareholders wish to set forth the terms
and conditions under which the Company may pay dividends to the Shareholders;
and

          WHEREAS, the Company and the Shareholders realize that, in the event
of the sale, transfer or encumbrance of a Shareholder's stock in the Company,
should the stock of the Company owned by such Shareholder pass into the
ownership or control of a person or entity other than the remaining
Shareholders, it would tend to disrupt the harmonious and successful management
and control of the Company; and

          WHEREAS, it is the earnest desire of the Company and the Shareholders
to assure to the remaining Shareholders a succession to the ownership and
control of the Company through the acquisition of the stock of a Shareholder
prior to such Shareholder's sale or encumbrance of the stock held by such
Shareholder.

          NOW, THEREFORE, in consideration of the premises, the mutual promises
of the parties hereto and the mutual benefits to be gained by the performance
thereof, and other good and valuable consideration, the receipt and sufficiency
of which are hereby acknowledged, the Company, for its successors and permitted
assigns, and the Shareholders, for themselves, their heirs, personal
representatives and permitted assigns, hereby agree as follows.

                                   ARTICLE I
                                  Definitions

          Whenever used in this Agreement, the following defined terms shall
have the meanings as set forth below in this Article:

1.01  "Affiliate" means any Person that, directly or indirectly, owns or
       ---------
Controls any other Person on an aggregate basis, including all beneficial
ownership and ownership or Control as a trustee, guardian or other fiduciary, or
that is controlled by or is under common control with such other Person.
<PAGE>

1.02  "Agreement" means this Shareholders Agreement and all schedules and
       ---------
exhibits hereto, if any, as from time to time hereafter further amended.

1.03  "Capital Contribution" means, with respect to a Shareholder, (i) any cash
       --------------------
or cash equivalents contributed to the Company with respect to such
Shareholder's Stock as provided herein, and (ii) the agreed fair market value,
net of liabilities secured by that contributed property that the Company is
considered to assume or to which such property is subject at the time of its
contribution to the Company, of any other property contributed to the capital of
the Company with respect to that Shareholder's Stock.

1.04  "Change of Control" means a sale of all or substantially all of the assets
      -------------------
and/or outstanding capital stock of MRTC and/or a merger in which MRTC is not
the surviving entity.

1.05  "Common Stock" means the Common Stock of the Company, no par value, which
       ------------
has the respective rights, preferences and restrictions specified with respect
to such Stock in this Agreement and the Certificate of Incorporation of the
Company.

1.06  "Closing Date" means the effective date on which the Company becomes the
       ------------
owner of more than fifty percent (50%) of all classes of stock of Coastal
Utilities, Inc., a Georgia corporation.

1.07  "Code" means the Internal Revenue Code of 1986, as amended and in effect
       ----
from time to time (and any corresponding provisions of succeeding law).

1.08  "Company" shall have the meaning set forth in the first paragraph of this
       -------
Agreement.

1.09  "Control" (including, with correlative meanings, the terms "controlled
       -------
by", "controlling" and "under common control with") means, as used with respect
to any Person, the possession, directly or indirectly, of the power to direct or
cause the direction of the management and policies of such Person, whether
through ownership of voting securities, by contract or otherwise.

1.10  "Depository" shall have the meaning set forth in Section 4.07.
       ----------

1.11  "Determination Date" shall have the meaning set forth in Section 4.04.
       ------------------

1.12  "Entity" means any corporation, partnership, limited liability company,
       ------
trust or trustee on behalf of a trust, unincorporated organization, association
or other entity, whether foreign or domestic.

1.13  "Fiscal Year" means the calendar year.
       -----------

1.14  "IPO" means an initial sale pursuant to an underwriting registration filed
       ---
under the Securities Act of 1933, as amended, of equity securities of an Entity.

1.15  "Lifetime Option Period" shall have the meaning set forth in Section 4.01.
       ----------------------
<PAGE>

1.16  "Liquidation Event" shall have the meaning set forth in Section 5.02.
       -----------------

1.17  "MRC" means Madison River Capital, LLC, a Delaware limited liability
       ---
company, and any successor Entity thereof.

1.18  "MRTC" means Madison River Telephone Company, LLC, a Delaware limited
       ----
liability company, and any successor Entity thereof.

1.19  "Person" means an individual, a custodian for any individual under any
       ------
jurisdiction's Uniform Transfers to Minors Act or similar statute, a
guardianship or guardian on behalf of a guardianship, an estate, or an Entity.

1.20  "Risk Changing Event" means any of the following events occurring after
       -------------------
November 23, 1999:  (i) a change of control with respect to MRTC, the Company
(but only if such change in control results in one or more parties that are not
Affiliates of MRTC being in control of the Company), or Coastal Utilities, Inc.,
a Georgia corporation (other than the Company's acquisition of the stock
thereof); (ii) any sale of all or substantially all (as described in the
commentary to the Model Business Corporation Act) of the assets of MRTC and its
subsidiary Affiliates on a consolidated basis in one transaction or series of
related transactions (but excluding sales to Affiliates) for cash or marketable
securities; (iii) a merger, consolidation, unit exchange or other transaction
which accomplishes one or more of the foregoing; (iv) the issuance or the
refinancing of any publicly traded debt by MRTC; (v) the closing of an
additional acquisition of a business by MRTC, MRC or the Company for an
aggregate consideration in excess of fifty million dollars ($50,000,000); (vi)
an IPO of MRTC; (vii) an IPO of the Company; or (viii) the dissolution of the
Company.

1.21  "Securities Act" means the Securities Act of 1933, as amended.
       --------------

1.22  "Series A Call Right" shall have the meaning set forth in Section 3.06.
       -------------------

1.23  "Series A Exercise Price" means the amount to be paid to the Series A
       -----------------------
Shareholders upon the exercise of the Series A Call Right or the Series A Put
Right, which amount is more fully set forth on Exhibit B hereto.
                                               ---------

1.24  "Series A Put Right" shall have the meaning set forth in Section 3.07.
       ------------------

1.25  "Series A Shareholder" means any Shareholder owning Series A Stock.
       --------------------
"Series A Shareholders" means such Persons as a group.
----------------------

1.26  "Series A Stock" means the Series A Common Stock of the Company, no par
       --------------
value, which has the respective rights, preferences and restrictions specified
with respect to such Stock in this Agreement and the Certificate of
Incorporation of the Company.

1.27  "Series B Call Right" shall have the meaning set forth in Section 3.02.
       -------------------

1.28  "Series B Put Right" shall have the meaning set forth in Section 3.02.
       ------------------
<PAGE>

1.29  "Series B Shareholder" means any Shareholder owning Series B Stock.
       --------------------
"Series B Shareholders" refers to such Persons as a group.
 ---------------------

1.30  "Series B Stock" means the Series B Common Stock of the Company, no par
       --------------
value, which has the respective rights, preferences and restrictions specified
with respect to such Stock in this Agreement and the Certificate of
Incorporation of the Company.

1.31  "Series C Capital Contribution" means the amount of any Capital
       -----------------------------
Contributions made to the Company by a Series C Shareholder.

1.32  "Series C Dividends" means, with respect to a Series C Shareholder, an
       ------------------
amount equal to 15% per annum (prorated for any partial year), compounded
annually, of the Series C Shareholder's total Unreturned Series C Capital
Contribution, outstanding from time to time during the period to which the
Series C Dividend relates.  Series C Dividends shall accrue from and after the
Company's receipt of a Shareholder's Series C Capital Contribution.

1.33  "Series C Shareholder" means MRC.
       --------------------

1.34  "Series C Stock" means the Series C Common Stock of the Company, no par
       --------------
value, which has the respective rights, preferences and restrictions specified
with respect to such Stock in this Agreement and the Certificate of
Incorporation of the Company.

1.35  "Shareholder" shall have the meaning set forth in the first paragraph of
       -----------
this Agreement.

1.36  "Stock" shall have the meaning set forth in Section 2.01.
       -----

1.37  "Unpaid Series C Dividends" means, with respect to a Series C Shareholder,
       -------------------------
an amount equal to the excess, if any, of:  (i) that Shareholder's aggregate
accrued Series C Dividends, over (ii) the aggregate prior dividends paid to such
Shareholder by the Company that constitute a payment of Series C Dividends
pursuant to Section 5.01.

1.38  "Unreturned Series C Capital Contribution" means, with respect to a Series
       ----------------------------------------
C Shareholder on any day, an amount equal to the excess, if any, of:  (i) the
aggregate amount of Series C Capital Contributions made by or with respect to
such Shareholder's Series C Stock; over (ii) the excess, of any, of (A) the
aggregate amount of prior dividends and other distributions paid by the Company
with respect to such Shareholder's Series C Stock over (B) the aggregate amount
of Series C Dividends accrued with respect to such Shareholder's Series C Stock.

                                  ARTICLE II
                                   Ownership

      2.01  Ownership of Shares.  The authorized capital stock of the
            -------------------
Company consists of three thousand three hundred shares of no par value Common
Stock (the "Common Stock"), three hundred (300) shares of which is designated as
            ------------
Series A Common Stock (the "Series A Stock"), three hundred (300) shares of
                            --------------
which is designated as Series B Common Stock (the "Series B Stock") and two
                                                   --------------
thousand seven hundred (2,700) shares of which is designated as Series C Common
Stock (the "Series C Stock"), the issued and outstanding shares of which are
            --------------
owned as of the date hereof
<PAGE>

by the Shareholders as shown and set forth in Exhibit A attached hereto. Exhibit
                                              ---------                  -------
A shall be deemed automatically amended by the Shareholders to reflect any
-
subsequent transfers of stock by or to them, or to add new shareholders, as
permitted by this Agreement. The shares of the Company's stock now or hereafter
owned by the Shareholders sometimes shall collectively be referred to herein as
the "Stock."
     -----

          2.02  Compliance with Securities Laws; Endorsement of Stock
                -----------------------------------------------------
Certificates.  Shareholders may transfer Stock hereunder only upon compliance
------------
with the terms of this Agreement and only if (a) such stock is registered under
the Securities Act of 1933, as amended (the "Securities Act"), and all
                                             --------------
applicable state securities acts, or (b) an exemption from registration is
available and an opinion of counsel satisfactory to the Company to that effect
is obtained and the provisions of Section 4.03 hereof are satisfied.  Upon the
execution of this Agreement, the stock certificates held by each of the
Shareholders representing the shares of Stock owned by each of them, if not
already so endorsed, shall be surrendered to the Company for endorsement
substantially as follows.

          "THE SHARES REPRESENTED BY THIS CERTIFICATE HAVE NOT BEEN REGISTERED
          UNDER THE SECURITIES ACT OF 1933, AS AMENDED, OR ANY STATE SECURITIES
          ACT AND MAY NOT BE SOLD, TRANSFERRED OR PLEDGED IN THE ABSENCE OF SUCH
          REGISTRATION UNLESS THE CORPORATION RECEIVES AN OPINION OF COUNSEL
          (WHICH MAY BE COUNSEL FOR THE CORPORATION) REASONABLY SATISFACTORY TO
          IT THAT SUCH TRANSFER MAY BE MADE IN COMPLIANCE WITH APPLICABLE
          FEDERAL AND STATE SECURITIES LAWS AND REGULATIONS.

          THE SHARES REPRESENTED BY THIS CERTIFICATE ARE SUBJECT TO THE TERMS
          AND PROVISIONS OF AN AGREEMENT AMONG THE CORPORATION AND CERTAIN OF
          ITS SHAREHOLDERS, AND ARE TRANSFERABLE ONLY IN ACCORDANCE WITH THE
          TERMS AND CONDITIONS OF SUCH AGREEMENT. A COPY OF SUCH AGREEMENT MAY
          BE EXAMINED IN THE OFFICE OF THE CORPORATION."

          After endorsement, the certificates shall be returned to the
Shareholders. Any and all stock certificates hereinafter governed by this
Agreement shall bear the same endorsement and shall be subject to the terms and
conditions of this Agreement.

                                  ARTICLE III
                                Put/Call Rights

          3.01  Transfer of Shares.  No Shareholder shall transfer, sell,
                ------------------
assign, encumber, pledge or in any way alienate any of the Stock, except as
provided herein.  Any transfer or encumbrance or attempted transfer or
encumbrance in violation of the terms of this Agreement shall be void and of no
force or effect whatsoever, and shall not transfer any interest in or title to
the purported transferee.  The Company shall not be required to transfer on its
books any Stock transferred in violation hereof or to treat as owner of such
Stock any transferee.  Notwithstanding the foregoing, any Shareholder may
transfer all or any part of his Stock in the Company to the trustee(s) of a
revocable trust agreement established by such Shareholder so long as (a) such
Shareholder retains the right to amend or revoke such revocable trust agreement
at any time, and (b) the trustee of such revocable trust agreement agrees in
writing to be bound by the terms of this Agreement.  All other
<PAGE>

transfers of the Stock must be approved by majority consent of the Series C
Shareholder, which approval shall not be unreasonably withheld.

          3.02  Series B Put/Call Rights Generally.  The Series B Stock shall
                ----------------------------------
carry certain rights whereby a holder of Series B Stock may require the Company
to purchase the Series B Stock (each a "Series B Put Right") and shall be
                                        ------------------
subject to certain provisions whereby a holder of Series B Stock may be required
to sell the Series B Stock (each a "Series B Call Right"), each as further
                                    -------------------
described in this Article III.  A Series B Put Right shall be exercised by the
Series B Shareholders giving written notice thereof to the Company, with a copy
to the holders of Series C Stock, in accordance with the provisions of Section
6.02.  A Series B Call Right shall be exercised by the Company's giving written
notice thereof to the Series B Shareholders in accordance with the provisions of
Section 6.02.  Upon valid exercise of a Series B Put Right or Series B Call
Right under this Article III, the Company shall pay cash to the Series B
Shareholders, in the amount of the put/call exercise price determined under this
Article III, by the date determined under Section 3.03; provided, however, the
                                                        --------  -------
Shareholders shall give any required notices to, make any filings with, and use
their best efforts to obtain any authorizations, consents, and approvals of
governments and governmental agencies in connection with all puts and calls
exercised pursuant to this Agreement.

          3.03  Series B Put/Call Payment Date.
                ------------------------------

                (a)  If a Series B Put Right or a Series B Call Right under this
Article III is validly exercised within one (1) year after the Closing Date, the
Company shall pay cash to the Series B Shareholders, in an amount equal to the
put/call exercise price determined under Sections 3.04 or 3.05.  In the case of
the exercise of a Put Right, the price shall be paid on the first business day
(i.e., a day on which federally chartered banks in the States of North Carolina
and Georgia are open) after the second anniversary of the Closing Date.  In the
case of the exercise of a Call Right, the price shall be paid within ten (10)
days of the exercise of the Call Right.

                (b)  If a Series B Put Right or a Series B Call Right under this
Article III is validly exercised after the first anniversary of the Closing Date
but within two (2) years after the Closing Date, the Company shall pay cash to
the Series B Shareholders, in an amount equal to the put/call exercise price
determined under Sections 3.04 or 3.05.  In the case of the exercise of a Put
Right, the price shall be paid by the later of (i) the first business day (i.e.,
a day on which federally chartered banks in the States of North Carolina and
Georgia are open) after the second anniversary of the Closing Date, or (ii)
three (3) months following the exercise date.  In the case of the exercise of a
Call Right, the price shall be paid within ten (10) days of the exercise of the
Call Right.

                (c)  If a Series B Put Right or a Series B Call Right under this
Article III is validly exercised after the second anniversary of the Closing
Date, the Company shall pay cash to the Series B Shareholders, in an amount
equal to the put/call exercise price determined under Sections 3.04 or 3.05.  In
the case of the exercise of a Put Right, the price shall be paid by the later of
(i) December 31st following the exercise date or (ii) three (3) months following
the exercise date.  In the case of the exercise of a Call Right, the price shall
be paid within ten (10) days of the exercise of the Call Right.
<PAGE>

          3.04  Series B Put Rights.
                -------------------

                (a)  Prior to the second anniversary of the Closing Date, the
Series B Put Rights shall be exercisable by the Series B Shareholders only
during (i) the nine (9)-month period beginning on the day after the occurrence
of a "Risk Changing Event", or (ii) if such "Risk Changing Event" shall have
      -------------------
occurred after November 23, 1999, but before the Closing Date, then during the
nine (9)-month period beginning after the Closing Date. The put exercise price
for all of the Series B Stock, if the Series B Put Right is exercised during
this time period, shall be $35,000,000.

                (b)  Beginning on the day after the fourth anniversary of the
Closing Date, the Series B Put Right shall be exercisable by the Series B
Stockholders at any time. The put exercise price for all of the Series B Stock,
if the Series B Put Right is exercised during this time period, shall be
$60,000,000.

                (c)  The Series B Put Right may be exercised during a valid
exercise period under Sections 3.04(a) or (b) above only by the majority consent
of the Series B Shareholders, and the exercise of the Series B Put Right under
this Section 3.04(c) shall be binding on all Persons holding Series B Stock.

          3.05  Series B Call Right.
                -------------------

                (a)  On or prior to the first anniversary of the Closing Date,
the Series B Call Right shall be exercisable upon the majority consent of the
Series C Shareholder only upon an IPO of securities of MRTC, a successor Entity
thereto, or an Affiliate of MRTC holding a direct or indirect interest in the
Company. If the Series B Call Right is exercised during this time period, the
call exercise price shall be $35,000,000.

                (b)  For the period beginning on the day after the first
anniversary of the Closing Date and ending on the date that is four (4) years
after the Closing Date, the Series B Call Right shall be exercisable by majority
consent of the Series C Shareholder at any time. If the Series B Call Right is
exercised during this time period, but on or prior to the second anniversary of
the Closing Date, the call exercise price shall be $45,000,000; if the Series B
Call Right is exercised after the second anniversary, but on or prior to the
third anniversary of the Closing Date, the call exercise price shall be
$50,000,000; and if the Series B Call Right is exercised after the third
anniversary, but on or prior to the fourth anniversary of the Closing Date, the
call exercise price shall be $55,000,000.

                (c)  For the period beginning on the day after the fourth
anniversary of the Closing Date and ending on the date that is five (5) years
after the Closing Date, the Series B Call Right shall be exercisable by majority
consent of the Series C Shareholder only upon an IPO of securities of MRTC, a
successor Entity thereto, or an Affiliate of MRTC holding a direct or indirect
interest in the Company. If the Series B Call Right is exercised during this
time period, the call exercise price shall be $60,000,000.

                (d)  Beginning on the day after the fifth anniversary of the
Closing Date, the Series B Call Right shall be exercisable by majority consent
of the Series C Shareholder at any
<PAGE>

time. If the Series B Call Right is exercised during this time period, the call
exercise price shall be $60,000,000.

          3.06  Series A Call Right.  Subject to the payment conditions of
                -------------------
Section 3.08, the Company may at any time require all holders of Series A Stock
to sell their Series A Stock to the Company in redemption of the entire Series A
Stock (a "Series A Call Right") by the Company's making payment to the Series A
          -------------------
Shareholders of the Series A Exercise Price.  A Series A Call Right shall be
exercised by the Company's giving written notice thereof to the Series A
Shareholders in accordance with the provisions of Section 6.02.

          3.07  Series A Put Right.
                ------------------

                (a)  At any time after the fifth anniversary of the Closing
Date, the Series A Shareholders may require the Company to purchase all of the
Series A Stock (a "Series A Put Right"), as further described in this Article
                   ------------------
III. A Series A Put Right shall be exercised by the Series A Shareholders giving
written notice thereof to the Company, with a copy to the Series C Shareholder,
in accordance with the provisions of Section 6.02.  Upon the exercise of the
Series A Put Right, the Company shall redeem all of the Series A Stock by making
payment to the Series A Shareholders of the Series A Exercise Price.

                (b)  The Series A Put Right may be exercised during a valid
exercise period under this Section 3.07 only by the majority consent of the
Series A Shareholders, and the exercise of the Series A Put Right under this
Section 3.07(b) shall be binding on all Persons holding Series A Stock.

          3.08  Series A Put/Call Payment Date.
                ------------------------------

                (a)  If a Series A Call Right under Section 3.06 is validly
exercised within one (1) year after the Closing Date, the Company shall pay cash
to the Series A Shareholders, in an amount equal to the Series A Exercise Price
determined under Section 3.06, by the later of (i) December 31st following the
exercise date or (ii) three (3) months following the exercise date.

                (b)  If a Series A Call Right under Section 3.06 is validly
exercised after the first anniversary of the Closing Date but within two (2)
years after the Closing Date, the Company shall pay cash to the Series A
Shareholders, in an amount equal to the Series A Exercise Price determined under
Section 3.06, by the later of (i) the first business day (i.e., a day on which
federally chartered banks in the States of North Carolina and Georgia are open)
after the second anniversary of the Closing Date or (ii) three (3) months
following the exercise date.

                (c)  If a Series A Call Right under Section 3.06 is validly
exercised after the second anniversary of the Closing Date or if a Series A Put
Right under Section 3.07 is validly exercised after the fifth anniversary of the
Closing Date, the Company shall pay cash to the Series A Shareholders, in an
amount equal to the Series A Exercise Price determined under Section 3.06 or
Section 3.07, by the later of (i) December 31st following the exercise date or
(ii) three (3) months following the exercise date.

          3.09  Exercise of Put Upon Dissolution.  The Series C Shareholder may
                --------------------------------
voluntarily dissolve the Company by majority consent of the Series C Shareholder
(which, as provided in
<PAGE>

Section 1.19, shall be a Risk Changing Event), provided that prior to any such
voluntary dissolution, written notice thereof must be given to the Series A and
Series B Shareholders in accordance with the provisions of Section 6.02, and
such Series A and Series B Shareholders must be granted thirty (30) days from
the date of receipt of the written notice to exercise any put rights available
to them under this Agreement.

                                  ARTICLE IV
                                Other Transfers

          4.01  Manner of Transfer.  Except for permitted transfers under
                ------------------
Section 3.01 of this Agreement, in the event that any Shareholder, or the estate
of a deceased Shareholder, desires to sell, exchange or otherwise convey for
consideration, or give, assign, pledge or otherwise transfer all or any part of
such Shareholder's Stock, including a voluntary or involuntary transfer in
connection with equitable distribution or similar proceedings, such Shareholder
shall first offer in writing for the period ending thirty (30) days after the
date of notice (the "Lifetime Option Period") all of such Shareholder's Stock to
                     ----------------------
the Company; provided that, notwithstanding any prior acceptance of the offer by
             --------
the Company, it may reject the offer within five (5) days of the determination
of the purchase price pursuant to Section 4.04 hereof. The method for allocating
the shares to be purchased by the Company shall be as described in Section 4.02.

          If the Company does not accept such offer to purchase all such Stock
so offered, the remaining Shareholders shall have a thirty (30)-day right,
beginning on the later of the day after the expiration of the Lifetime Option
Period or the Company's express rejection of the offer following determination
of the purchase price, to purchase all such Stock.  This offer shall be at a
price and on terms determined in accordance with the provisions of Sections 4.04
and 4.05 hereof; provided that, notwithstanding any prior acceptance of the
                 --------
offer by the remaining Shareholders, they may reject the offer within five (5)
days of the determination of the purchase price pursuant to Section 4.04 hereof.

          If all such Stock is not accepted for purchase by the remaining
Shareholders or by the Company within said option periods, the Shareholder
desiring to sell or otherwise dispose of his Stock may sell or otherwise dispose
of such Shareholder's Stock to any other person or persons, but shall not sell
it for a lower price than that initially determined under Section 4.04 hereof
without first giving the remaining Shareholders the primary right, and the
Company a secondary right if the remaining Shareholders do not exercise their
primary right, for a period of thirty (30) days from notice of such right, to
purchase such Stock at the price and on the terms offered to such other persons.
Notwithstanding the forgoing, any transfer of Stock of the Company shall be
subject to the approval of the Series C Shareholder, which approval shall not be
unreasonably withheld.

          Any transfer in accordance with this Section 4.01 shall also be
subject to the conditions set forth in Section 4.03, below.

          4.02. Allocation of Shares among Purchasing Shareholders.  In the
                --------------------------------------------------
event any Stock is to be purchased by a group of Shareholders hereunder, such
Stock shall be purchasable by each Shareholder in the proportion that the shares
of Stock then owned by each such purchasing Shareholder bears to the shares of
Stock owned by all the remaining Shareholders (excluding the selling
Shareholder), unless otherwise mutually agreed among all remaining Shareholders.
If one or more of such Shareholders signify their intention to accept such
offer, and other Shareholders fail to
<PAGE>

accept such offer, then each of the accepting Shareholders shall have the right
to purchase all such Stock from the offeror, for a period of thirty (30) days
after the date the applicable option period otherwise would have expired (and
such option period shall automatically be extended by such thirty (30)-day
period), in the proportion that the shares of Stock then owned by such
purchasing Shareholder bears to the shares of Stock owned by all the purchasing
Shareholders, unless otherwise mutually agreed among all such purchasing
Shareholders.

          4.03  Transferee Restrictions.  Any transferee of Stock under this
                -----------------------
Agreement must become a "Shareholder" party to this Agreement by executing any
instruments or documents that may be deemed necessary or advisable by counsel to
the Company to make such transferee a party to this Agreement, or such transfer
shall be deemed null and void.

          4.04  Purchase Price for Stock.  The purchase price to be paid for
                ------------------------
Stock purchased according to this Agreement shall be the amount offered in
writing to be paid for such Stock by the unaffiliated purchaser.

          The determination date for the purpose of establishing the purchase
price hereunder shall be the date on which the transferring Shareholder offers
to transfer his stock to the remaining Shareholders, or the Company as the case
may be, according to Section 4.01 hereof (the "Determination Date").
                                               ------------------

          4.05  Terms of Payment.  In the event Stock shall be purchasable from
                ----------------
a Shareholder under Section 4.01 on account of the proposed sale of his Stock
during his lifetime or existence, the terms of sale of the Stock shall be the
terms offered in writing by the unaffiliated purchaser.

          4.06  Title to Stock Under Installment Payment.  Title to any Stock
                ----------------------------------------
subject to an installment payment shall be transferred to the purchaser(s).
However, until full payment of the purchase price of such Stock is made by the
purchaser(s), each purchaser shall at the closing of such purchase endorse the
share certificates for the Stock purchased by such purchaser in blank and
deposit such share certificates with the Depository, as hereinafter defined,
upon terms and conditions mutually acceptable to the seller, the purchaser and
the Depository as security for the obligations of the purchaser.  Nevertheless,
so long as a purchaser is not in default hereunder or under the obligations
relating to payment for the Stock, such Stock shall be voted by such purchaser,
and all regular dividends declared and paid on such Stock or distributions made
to the purchaser, shall be applied, first, on account of any interest that may
be due from such purchaser and, second, on account of installments of the
purchase price in the inverse order of maturity.  However, upon default of an
individual purchaser, and so long as a default of such individual purchaser
remains uncured, the transferring Shareholder or the personal representative of
the estate of a deceased Shareholder shall be permitted to vote such Stock, and
each purchaser shall execute at the time of transfer irrevocable proxies in
favor of the transferring Shareholder or the personal representative of the
estate of a deceased Shareholder to this effect.  In the event of any default by
an individual purchaser, the seller of such Stock may direct the Depository, as
hereinafter defined, to sell all such individual purchaser's Stock at public or
private sale on notice to such purchaser.  At such sale, the seller of such
Stock may become the purchaser of such Stock and apply on account of the bid
price any unpaid portion of the purchase price and interest due thereon.  From
the net proceeds of such sale, after the payment of all expenses of the
Depository and all expenses of the sale, there shall be paid to the seller the
unpaid portion of the purchase price and all interest due thereon, and any
excess shall be paid to the purchaser.  If there is any deficiency, the
purchaser shall
<PAGE>

remain liable to the seller. The foregoing remedy shall not be exclusive, and
the seller of such Stock may resort to any other legal as well as equitable
remedy available under the law.

          4.07  Closing of Purchase.  Within thirty (30) days following the
                -------------------
offer and acceptance of an offer to sell Stock in accordance with the provisions
of Article IV of this Agreement, or within thirty (30) days following the
exercise of any option or options to purchase the Stock of a Shareholder, as the
case may be, the purchaser(s) of such Stock shall tender the purchase price for
such Stock, to counsel designated by the Company (hereinabove and hereinafter
referred to as the "Depository"), and the transferring Shareholder or the
                    ----------
personal representative of a deceased Shareholder's estate, as the case may be,
shall deliver to the Depository:

                (a)  The certificate or certificates evidencing the Stock held
or owned by the transferor Shareholder either duly endorsed in blank or with
appropriate blank stock powers properly executed; and

                (b)  Any and all other documents that reasonably may be required
by the Company and remaining Shareholders in connection with the transfer of the
shares of the transferor.

          Upon receipt of such certificates and other documents, the Depository
shall deliver the purchase price for such Stock to the transferor of such Stock
and shall deliver the stock certificates to the purchaser(s), and shall
thereupon be relieved of any and all further duties hereunder.

          4.08  Indemnity of Transferring Shareholder.  The remaining
                -------------------------------------
Shareholders and the Company shall jointly and severally defend, indemnify and
hold harmless each Shareholder transferring shares hereunder to the remaining
Shareholders or to the Company from and against all claims, demands, suits,
obligations, liabilities, damages, losses and judgments, including out-of-pocket
costs and expenses and reasonable attorneys' fees incident thereto for which the
transferring Shareholder personally was a guarantor, pledgor, endorser or co-
signer and that were in any way connected with the debts and obligations of the
Company incurred in the ordinary course of business by the Company or upon
authorization of the Board of Directors of the Company.

                                   ARTICLE V
                           Dividends and Liquidation

          5.01  Dividends.  Dividends by the Company to and among the
                ---------
Shareholders, other than dividends in connection with the liquidation and
winding up of the Company, shall be in accordance with the provisions of this
Section 5.01.  Subject to any restrictions or limitations mandatorily imposed on
the Company by the Delaware General Corporation Law and any restrictions
contained in any financing agreements to which the Company or any of its
Affiliates is a party, the Board of Directors may, in its sole and absolute
discretion, cause the Company to pay dividends to the Shareholders at any time
and from time to time.  Any such dividends shall first be applied to the payment
to the Series C Shareholder(s) of an amount equal to the Unpaid Series C
Dividends, if any, as determined immediately prior to such dividends (which, if
there is more than one Shareholder having Unpaid Series C Dividends at such
time, shall be distributed among all such Shareholders in proportion to their
respective amounts, if any, of Unpaid Series C Dividends).  Any balance after
payment of the Unpaid Series C Dividends shall be paid ten percent (10%) to the
Series B Shareholders, to be paid among such Shareholders in proportion to
<PAGE>

their respective percentages of ownership of Series B Stock, and ninety percent
(90%) to the Series C Shareholder.

          5.02  Events Causing Liquidation.  The Company shall be liquidated
                ---------------------------
upon the first to occur of the following events (a "Liquidation Event"):
                                                    -----------------

                (a)  The sale or disposition of all or substantially all of the
assets (other than cash or cash equivalents) of the Company in a single
transaction or a series of related transactions, and the determination to
distribute all proceeds of any such transaction(s) in accordance with the terms
of this Agreement;

                (b)  The majority consent of the Series C Shareholder; provided,
                                                                       --------
that prior to any such liquidation, written notice thereof must be given to the
Series A and Series B Shareholders in accordance with the provisions of Section
6.02, and such Series A and Series B Shareholders must be granted thirty (30)
days from the date of receipt of the written notice to exercise any put rights
available to them under this Agreement; or

                (c)  The entry of a decree of judicial dissolution of the
Company by a court of competent jurisdiction.

          5.03  Liquidation.  Upon the occurrence of a Liquidation Event, the
                -----------
Board of Directors shall act as liquidator or may appoint another Person to act
as liquidator in the Board of Directors' sole discretion, which liquidator shall
be subject to the Board of Directors' direction and control.  The liquidator
shall proceed diligently to wind up the affairs of the Company and make final
distributions as provided herein and under Delaware law.  The costs of
liquidation shall be borne as a Company expense.  Until such distribution, the
liquidator shall continue to operate the Company, subject to the direction and
control of the Board of Directors.  The liquidator shall undertake the
following:

                (a)  as promptly as possible after dissolution and again after
final liquidation, the liquidator shall cause a proper accounting to be made, by
the Company's independent accountants, of the Company's assets, liabilities and
operations through the last day of the calendar month in which the liquidation
occurs or the final liquidation is completed, as applicable;

                (b)  the liquidator shall pay, satisfy or discharge from Company
funds all of the debts, liabilities and obligations of the Company or otherwise
make adequate provision for payment and discharge thereof (including, without
limitation, the establishment of a cash fund for contingent liabilities in such
amount and for such term as the liquidator may reasonably determine); and

                (c)  upon the payment of the debts, liabilities and obligations
of the Company, the liquidator shall distribute any balance to and among the
Shareholders as follows: so long as each Series of Stock shall be outstanding,
(1) 10% to the Series A Shareholders; (2) 20% to the Series B Shareholders; and
(3) 70% to the Series C Shareholder; provided, however, if any Series of Stock
                                     --------  -------
is not outstanding, then such balance shall be proportionately recalculated and
distributed among the remaining Series of Stock.  By way of example and not
limitation, if at the time of liquidation, the Series B Put Right has been
exercised, then the Series A Shareholders
<PAGE>

would be entitled to one-eighth of the balance that would have been paid to the
Series B Shareholder, with the Series A Shareholders receiving 12.5% and the
Series C Shareholder receiving 87.5%.

          5.04  Reasonable Time for Winding Up.  A reasonable time shall be
                ------------------------------
allowed for the orderly winding up of the business and affairs of the Company
and the liquidation of its assets pursuant to Section 5.03 in order to minimize
any losses otherwise attendant upon such winding up.

                                  ARTICLE VI
                                 Miscellaneous

          6.01  Term.  This Agreement shall continue as long as at least two (2)
                ----
of the Shareholders are living, organized and/or existing and own shares of
Stock.

          This Agreement shall terminate upon the occurrence of:

               (a)  The bankruptcy, receivership or dissolution of the Company;

               (b)  The sale of all the Stock covered by this Agreement to the
                    Company;

               (c)  Upon the written agreement of the Company and the
                    Shareholders holding at least sixty-six and two-thirds
                    percent (66-2/3%) of each Series of Stock to that effect; or

               (d)  The effective date of a Company firm commitment IPO (which,
                    as provided in Section 1.20, shall be a Risk Changing
                    Event); provided that prior to any such IPO, written notice
                            --------
                    thereof must be given to all Shareholders in accordance with
                    the provisions of Section 6.02, and the Shareholders shall
                    have thirty (30) days from the date of receipt of the
                    written notice to exercise any put or call rights available
                    to them under this Agreement.

          If and when all the Stock of a Shareholder shall have been transferred
in accordance with the terms and conditions of this Agreement, he or it shall
cease to be a party to this Agreement.

          6.02  Notices.  Any notice, offer, payment, demand, or other
                -------
communication required or permitted to be given by any provision of this
Agreement shall be deemed to have been delivered and given for all purposes (i)
if delivered personally to the party or to an officer of the party to whom the
same is directed or (ii) whether or not the same is actually received, if sent
by confirmed telecopy or telex or by registered or certified mail, return
receipt requested, postage and charges prepaid, or sent by Federal Express or
similar overnight national courier, addressed as follows:
<PAGE>

          If to the Company or MRC, at:

               103 South Fifth Street
               Mebane, North Carolina 27302
               Telecopy No.:  (919) 563-4993

          With a copy to:

               Madison River Capital, LLC
               103 South Fifth Street
               Mebane, North Carolina 27302
               Attention: Vice President and General Counsel
               Telecopy No.: (919) 563-4993

          If to any other Shareholder, as follows:

Daniel M. Bryant                                  G. Allan Bryant
P.O. Box 280                                      P.O. Box 899
Hinesville, Georgia 31310                         Allenhurst, Georgia 31301
Telecopy No.:______________                       Telecopy No.:_______________

The Michael E. Bryant Life Trust
c/o Thomas J. Ratcliffe, Jr.
P.O. Box 969
Hinesville, Georgia 31313
Telecopy No.:______________

     Notices shall be deemed to have been given as of the date delivered or
sent, if delivered personally or sent by telecopy or telex, or the first
business day following deposit with Federal Express or similar overnight
courier, or seven (7) days after the date on which the same was deposited in a
regularly maintained receptacle for the deposit of mail, addressed and sent as
set forth above.  Each party may change the address set forth above for notices
upon written notice to all other parties hereto.

     6.03 Waiver of Breach.  The waiver by any party hereto of a breach of any
          ----------------
provision of this Agreement shall not operate or be construed as a waiver of any
subsequent breach by any party.

     6.04 Delegation; Assignment.  Except as set forth in this Section, no party
          ----------------------
to this Agreement shall delegate or assign any duties or rights under this
Agreement without the prior written consent of all parties to this Agreement.
Any such delegation or assignment without the prior written consent of all
parties to this Agreement shall be void.  No such consent of the parties to this
Agreement shall release the party delegating or assigning duties or rights from
his duties hereunder and such party shall continue to be jointly and severally
liable with the person to whom he has delegated duties for all defaults and
breaches of this Agreement by either of them.  Notwithstanding the foregoing, if
a right arises in the Company to purchase any Stock, the Company may assign such
right to another person or entity, who need not be a Shareholder, and such
assignee may exercise the right of the Company hereunder with respect to such
purchase option as fully as the Company, subject to compliance with Section
4.03.
<PAGE>

     6.05 Binding Effect.  This Agreement shall inure to the benefit of, and be
          --------------
binding upon, the parties hereto, their heirs, personal representatives,
successors and permitted assigns, and said parties agree to execute any
instrument in writing that may be necessary or proper in the carrying out of the
purposes and intent of this Agreement.

     6.06 State Law.  This Agreement shall be subject to and shall be construed
          ---------
under the Delaware General Corporation Law and other laws of the State of
Delaware, without regard to conflicts of law provisions.

     6.07 Disputes; Deadlock; Arbitration.  If a dispute should arise under this
          -------------------------------
Agreement between two (2) or more parties, or if a Shareholder reasonably
determines that the Company is unable to act on any material matter due to an
irreconcilable conflict among the Shareholders having equal voting power, then
any such party may make a demand for binding arbitration before the American
Arbitration Association in accordance with its then applicable rules by filing a
demand, in writing, with the other party or parties.  Any such arbitration shall
take place in Atlanta, Georgia, and the hearing before the arbitrator(s) of the
matter to be arbitrated shall be at the time and place within such county as is
selected by the arbitrator(s).  A judgment confirming the award of the
arbitrator(s) may be rendered by any court having jurisdiction.  Except as
otherwise specifically allocated under this Agreement, the costs of such
arbitration shall be borne by the party whose last position prior to the
commencement of the arbitration is farthest away from the decision of the
arbitrator(s), or in such proportions as the arbitrator(s) shall determine.

     6.08 Specific Performance.  The parties acknowledge that the actual damage
          --------------------
that would be sustained upon breach of the stock transfer restrictions of this
Agreement by any of the parties hereto cannot be expressed in monetary terms
and, therefore, any party aggrieved by the breach or threatened breach of any
such provision shall be entitled to seek from any court of competent
jurisdiction an order for specific performance of all the terms and conditions
of this Agreement.

     6.09 Effect of Noncompliance.  In the event of any purported or attempted
          -----------------------
transfer of Stock that does not comply with the provisions of this Agreement,
the attempted transfer shall be null and void and the purported transferee shall
not be deemed to be a shareholder of the Company and shall not be entitled to
receive a new stock certificate or any dividends or other distributions on or
with respect to the Stock.  However, any such purported or attempted transfer of
Stock shall, in addition, be deemed to be an irrevocable offer to sell such
Stock to the Company and/or remaining Shareholders, which the Company and/or
remaining Shareholders may accept pursuant to and in accordance with the terms
of Section 4.01 hereof, except that such Shareholder attempting any such
transfer shall not be permitted to sell, assign, pledge, dispose or transfer
such Stock to any other person in the event the Company and/or remaining
Shareholders do not accept such offer except in accordance with Section 4.01
hereof.

     6.10 Entire Agreement.  This Agreement contains the entire understanding
          ----------------
among the parties with respect to the subject matter hereof and supersedes any
prior agreement between the parties hereto concerning the sale or exchange of
Stock of the Company and any prior agreement shall be rendered null and void
upon the execution of this Agreement.

     6.11 Additional Securities.   Except as otherwise provided herein, this
          ---------------------
Agreement shall apply with equal force to all shares of capital stock of the
Company that may be subsequently issued
<PAGE>

to the Shareholders, and furthermore, shall continue to apply to shares now
issued, notwithstanding any transfer of shares as contemplated herein.

     6.12 Severability.  The invalidity or unenforceability of any particular
          ------------
provision of this Agreement shall not affect the other provisions hereof, and
the Agreement shall be construed in all respects as if such invalid or
unenforceable provisions were omitted.

     6.13 Purchase by the Company.  Notwithstanding any provision set forth in
          -----------------------
this Agreement to the contrary, in the event the Company purchases any stock
hereunder, all certificates evidencing the Stock so purchased shall be canceled
of record.

     6.14 Construction.  In the construction of this Agreement, the masculine
          ------------
gender shall include the feminine or the neuter in all cases where such meanings
would be appropriate. Any reference contained in this Agreement to specific
statutory or regulatory provisions or to specific governmental agencies or
entities shall include any successor statute or regulation, or agency or entity,
as the case may be. Unless otherwise specified, the references to "Section" and
"Article" in this Agreement are to the Sections and Articles of this Agreement.
When used in this Agreement, words such as "herein", "hereinafter", "hereof",
"hereto", and "hereunder" shall refer to this Agreement as a whole, unless the
context clearly requires otherwise. The use of the words "include" or
"including" in this Agreement shall be by way of example rather than by
limitation.

     6.15 Amendment.  This Agreement shall not be modified or amended, nor shall
          ---------
the operation of any provision hereof be waived, except (a) by a writing signed
by the party against whom enforcement is sought, or (b) by a writing signed by
the Shareholders holding at least sixty-six and two-thirds percent (66-2/3%) of
each Series of Stock, which modification or amendment shall be binding upon and
is hereby consented to by all Shareholders; provided, however, that no amendment
                                            --------  -------
shall affect the Put/Call Rights contained in Article III of this Agreement
without the written consent of the Shareholders.

     6.16 Counterparts.  This Agreement may be executed in counterparts, each of
          ------------
which shall be deemed an original hereof but all of which together constitute
one and the same instrument.

     6.17 Debt to Equity Ratio and Prohibition on Transfer of Stock of Coastal
          --------------------------------------------------------------------
Utilities, Inc.  The Company shall not increase the debt/equity ratio of Coastal
---------------
Utilities, Inc. ("CUI") above such ratio as existed on the Closing Date without
                  ---
the majority consent of each Series of Stock.  For purposes of calculating
debt/equity ratio as of the Closing Date, debt shall include all of CUI?s
committed long- and short-term debt, whether or not advanced as of the Closing
Date.  Except for existing pledges of the CUI stock to the Rural Telephone
Finance Cooperative (and pledges contemplated in connection with the closing of
the Company's purchase of all of the outstanding stock of CUI), for a period of
two (2) years from the Closing Date, the Company shall not create or permit any
lien, encumbrance, charge or security interest of any kind to exist on any of
the issued and outstanding stock of CUI.

                     [The next page is the signature page]
<PAGE>

     IN WITNESS WHEREOF, the Company and the Shareholders have executed this
Shareholders Agreement effective as of the day and year first above written.

                             COMPANY:
                             -------


                             COASTAL COMMUNICATIONS, INC.


                             By: /s/ PAUL H. SUNU
                                 --------------------------------
                             Name:   Paul H. Sunu
                                   ------------------------------
                             Title:  Chairman/CEO
                                    -----------------------------


                             SHAREHOLDERS:
                             ------------


                             MADISON RIVER CAPITAL, LLC


                             By: /s/ J. STEPHEN VANDERWOUDE
                                 --------------------------------
                             Name:   J. Stephen Vanderwoude
                                   ------------------------------
                             Title:  Manager
                                    -----------------------------


                              DANIEL M. BRYANT             (SEAL)
                             ------------------------------
                             Daniel M. Bryant


                              G. ALLAN BRYANT              (SEAL)
                             ------------------------------
                             G. Allan Bryant


                             MICHAEL E. BRYANT LIFE TRUST


                         By:  G. ALLAN BRYANT
                             --------------------------------------
                             Co-Trustee for Michael E. Bryant


                         By:  DANIEL M. BRYANT
                             --------------------------------------
                             Co-Trustee for Michael E. Bryant


                         By:  THOMAS J. RATCLIFFE, JR
                             --------------------------------------
                             Co-Trustee for Michael E. Bryant
<PAGE>

                                   Exhibit A
                                   ---------

                            SHAREHOLDERS AGREEMENT

                     ISSUED AND OUTSTANDING CAPITAL STOCK

                                     AS OF

                                March 30, 2000


<TABLE>
<CAPTION>
----------------------------------------------------------------------------------------------------------------------
    Name of Shareholder                   Address                       Number of Shares           Series of Stock
    -------------------                   -------                       ----------------           ---------------
----------------------------------------------------------------------------------------------------------------------
<S>                                    <C>                            <C>                       <C>
Daniel M. Bryant                       P.O. Box 280                          100 Shares                  Series A
                                                                      ------------------------------------------------
                                       Hinesville, Georgia 31310             100 Shares                  Series B
----------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------
G. Allan Bryant                        P.O. Box 899                          100 Shares                  Series A
                                                                      ------------------------------------------------
                                       Allenhurst, Georgia 31301             100 Shares                  Series B
----------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------
The Michael E. Bryant                  c/o Thomas J. Ratcliffe, Jr.          100 Shares                  Series A
Life Trust                             P.O. Box 969
                                                                      ------------------------------------------------
                                       Hinesville, Georgia  31313            100 Shares                  Series B
----------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------
Madison River Capital,                 103 South Fifth Street               2,700 Shares                 Series C
LLC                                    Mebane, NC  27302
----------------------------------------------------------------------------------------------------------------------
</TABLE>
<PAGE>

                                   Exhibit B
                                   ---------

                            SHAREHOLDERS AGREEMENT

                            SERIES A EXERCISE PRICE


     In the event the Company exercises the Series A Call Right pursuant to
Section 3.06 of the Agreement, the Company shall pay the Series A Shareholders
as follows: (i) on or before the first anniversary of the execution of the
Agreement, $11,000,000; (ii) after the first anniversary, and on or before the
second anniversary of the execution of the Agreement, $12,100,000; (iii) after
the second anniversary, and on or before the third anniversary of the execution
of the Agreement, $13,300,000; (iv) after the third anniversary, and on or
before the fourth anniversary of the execution of the Agreement, $14,600,000;
(v) after the fourth anniversary, and on or before the fifth anniversary of the
execution of the Agreement, $16,100,000; and (vi) anytime after the fifth
anniversary of the execution of the Agreement, $17,700,000.

     In the event the Series A Shareholders exercise the Series A Put Right
pursuant to Section 3.07 of the Agreement, the Company shall pay the Series A
Shareholders $17,700,000.