EXHIBIT A
                                   =========

                            STOCK EXCHANGE AGREEMENT
                         (WITH EXHIBITS AND AMENDMENTS)

 
                            STOCK EXCHANGE AGREEMENT


   THIS STOCK EXCHANGE AGREEMENT (this "Agreement") made this 29th day of April,
1997, is by and between Matrix Telecom, Inc. ("Matrix") and AvTel 
                                               ------            
Communications, Inc. ("Avtel").
                       -----   

1.     STOCK EXCHANGE

       At Closing (as hereinafter defined), the stockholders of Matrix listed on
                                                                                
       Schedule I (the "Stockholders") will deliver to Avtel 3,484,260 properly
       ----------       ------------                                           
       endorsed, unencumbered Matrix common shares (the "Stock"), representing
                                                         -----                
       100% of the outstanding Matrix common stock, in exchange for 34,590,049
       shares of common stock of Avtel (such numbers to be adjusted to give
       effect to the Merger and Reverse Stock Split (defined below)), which will
       not be registered under the Securities Act of 1933, as amended.

2.     EXCHANGE STATEMENT

       Prior to the Closing, Matrix shall deliver to Avtel a duly executed
       EXCHANGE STATEMENT from each Stockholder in the form attached hereto as
       Exhibit A (each, an "Exchange Statement").
       ---------            ------------------   

3.     MATRIX NON-QUALIFIED STOCK OPTIONS

       At Closing, Matrix will cancel all non-qualified stock options (covering
       9,000 Matrix shares) that it has granted and that remain outstanding as
       of the date hereof, and Avtel will issue to the beneficiaries thereof,
       89,348 Avtel non-qualified stock options (such numbers to be adjusted to
       give effect to the Merger and Reverse Stock Split (defined below)) having
       the same exercise period and exercise prices as currently apply to such
       Matrix options all as set forth on Schedule II.
                                          ----------- 

4.     REGISTRATION RIGHTS AND LOCK-UP AGREEMENTS

       At Closing, Avtel and Matrix, on behalf of the Stockholders, shall enter
       into a REGISTRATION RIGHTS AND LOCK-UP AGREEMENT in the form set forth on
       Exhibit B.
       --------- 

5.     MATRIX OPERATIONS; INVESTMENT PURPOSES

       Avtel will own Matrix and operate its business in the ordinary course and
       has no intention of disposing of significant assets.

6.     POOLING OF INTERESTS

       The parties intend that the transaction contemplated hereby will be
       treated as a pooling of interests and agree to abide by the restrictions
       contained in Accounting Series Release 135 ("ASR 135").  In this
                                                    -------            
       connection, no Stockholder will be allowed to sell any Avtel shares prior
       to release of Avtel and Matrix combined earnings covering a period of
       combined earnings of not less than 30 days in accordance with ASR 135.

7.     INCOME TAX TREATMENT

       The parties intend that the transaction will be treated as a tax-free
       reorganization under IRC Section 368(a)(1)(B) and will take no actions
       that will violate applicable requirements.

8.     AVTEL SHAREHOLDERS' MEETING

       Avtel shall, in accordance with applicable law, as soon as practicable:

         (a)   duly call, give notice of, convene and hold a special meeting of
               its stockholders (the "Stockholders' Meeting") for the purpose of
                                      ---------------------                     
               considering and taking action upon this Agreement;

                                      A-1

 
         (b)   subject to the fiduciary duties of the Board of Directors of
               Avtel under applicable law, include in a proxy statement (the
               "Proxy Statement") to be distributed to its stockholders the
                ---------------
               recommendation of the Board of Directors of Avtel that the
               stockholders of Avtel vote in favor of the approval and adoption
               of this Agreement and the transactions contemplated hereby;

         (c)   provide Matrix with copies of the proposed Proxy Statement and a
               reasonable opportunity to review and comment upon such Proxy
               Statement before it is mailed to Avtel's shareholders; and

         (d)   use its best efforts to (i) obtain and furnish the information
               required to be included by it in the Proxy Statement and respond
               promptly to any comments made by the Securities and Exchange
               Commission with respect to the Proxy Statement and any
               preliminary version thereof and cause the Proxy Statement to be
               mailed to its stockholders at the earliest practicable time and
               (ii) obtain the necessary approvals by its stockholders of this
               Agreement and the transactions contemplated hereby.

9.     AVTEL MERGER; REVERSE STOCK SPLIT

       (a)      Prior to the Closing hereunder, Avtel shall merge (the "Merger")
                                                                        ------  
                with and into a Delaware corporation, whereupon the separate
                corporate existence of Avtel shall cease and such Delaware
                corporation (hereinafter, "Newco") shall continue as the
                                           -----                        
                surviving corporation.  The Merger shall have the effects set
                forth under the laws of the State of Delaware.  Without limiting
                the generality of the foregoing, and subject thereto, all the
                properties, rights, privileges, powers and franchises of Avtel
                shall vest in Newco, and all debts, liabilities and duties of
                Avtel shall become the debts, liabilities and duties of Newco.
                The certificate of incorporation and bylaws of Newco shall be
                the certificate of incorporation and bylaws of the pre-existing
                Delaware corporation, substantially in the form agreed to prior
                to the Merger by Matrix and Avtel and approved by the
                shareholders of Avtel at the Stockholder's Meeting.  Subject to
                clause (b) below, at the effective time of the Merger, by virtue
                ----------                                                      
                of the Merger and without any action on the part of Avtel or
                Newco or the stockholders of Avtel, each share of common stock
                and preferred stock and each option of Avtel issued and
                outstanding immediately prior to the effective time of the
                Merger shall by virtue of the Merger be canceled and
                extinguished and be converted into the right to receive one
                share of the common stock or preferred stock or an option to
                acquire one share of common stock of Avtel, as applicable, of
                Newco.

       (b)      Subject to the approval of Avtel's stockholders at the
                Stockholders' Meeting, prior to the Closing, Avtel shall either
                (i) effect a reverse stock split pursuant to which each share of
                Avtel common stock and preferred stock and each option granted
                by Avtel to acquire Avtel common stock shall be converted into
                the right to receive such lesser amount of Avtel common stock,
                preferred stock or an option to acquire a lesser amount of Avtel
                common stock, as applicable, as Avtel and Matrix shall agree or,
                (ii) reduce the number of common stock, preferred stock or
                options to acquire Newco common stock that will be issued to
                Avtel stockholders in the Merger to such lesser number of shares
                of common stock, preferred stock or options to acquire Newco
                common stock as Avtel and Matrix shall agree (the adjustment
                contemplated by clauses (i) or (ii) being referred to herein as
                                -----------    ----
                the "Reverse Stock Split"). At such time as Avtel and Matrix
                shall agree upon the details of the Reverse Stock Split, Avtel
                and Matrix shall amend this Agreement to adjust the number of
                shares of Avtel common stock issuable to the stockholders of
                Matrix pursuant to this Section 1 and the number of shares of
                                        ---------
                Avtel common stock for which Avtel is required to grant options
                to holders of Matrix options pursuant to Section 3, in each
                                                         ---------
                case, in a manner which is directly proportional to the
                adjustments made to the Avtel common stock and options to
                acquire Avtel common stock pursuant to the Reserve Stock Split.


10.    AVTEL TO SUPPLY INFORMATION

       Until the Closing Date (as hereinafter defined), Avtel shall give Matrix
       full access during normal business hours, without unreasonable
       interference with business operations, to all of its the facilities,
       properties, books, contracts, commitments and records and shall make its
       officers and employees available to Matrix, 

                                      A-2

 
       as Matrix shall from time to time reasonably request. Matrix and its
       representatives will be furnished all information concerning Avtel that
       Matrix reasonably requests.

11.    MATRIX TO SUPPLY INFORMATION

       Until the Closing Date, Matrix shall give Avtel full access during normal
       business hours, without unreasonable interference with business
       operations, to all of its the facilities, properties, books, contracts,
       commitments and records and shall make its officers and employees
       available to Avtel, as Avtel shall from time to time reasonably request.
       Avtel and its representatives will be furnished all information
       concerning Matrix that Avtel reasonably requests.  Matrix shall provide
       to Avtel such information as may be required by the Proxy Statement which
       information shall be true and accurate in all material respects.

12.    BRIDGE LOAN

       Matrix agrees that following the execution of this Agreement, Matrix will
       make a bridge loan available to Avtel in the maximum principal amount of
       $500,000 on the following terms:

       (a)  Up to $250,000 may be drawn by Avtel any time after the execution
            of this Agreement and prior to the earlier to occur of (i) August
            31, 1997 or (ii) the termination of this Agreement.

       (b)  Up to an additional $250,000 may be drawn by Avtel at any time on
            or after July 1, 1997 and prior to the earlier to occur of (i)
            August 31, 1997 or (ii) the termination of this Agreement.

       (c)  Disbursements shall be made on five days' written notice to
            Matrix. No disbursements shall be made after the termination of
            this Agreement.

       (d)  The loan shall be recourse and shall bear interest at the rate of
            8% per annum through August 31, 1997, and thereafter at a rate of
            12% until maturity and, after maturity at a rate of 15%, in all
            cases subject to reduction to comply with applicable usury laws.
            Interest shall be payable monthly in arrears, based on a 360-day
            year, and all principal and accrued interest shall be due and
            payable on or before the earlier of (i) 180 days after the
            termination of this Agreement or (ii) December 1, 1997.

       (e)  Avtel shall pay all expenses of documenting the loan, including
            any necessary California usury permit, if any.

13.    MATRIX REPRESENTATIONS

       Matrix represents to Avtel as follows:

       (a)  Schedule I is a complete and accurate list of all of the shares of
            ----------                                                        
            Matrix common stock owned by each of the Stockholders.  Schedule II
                                                                    -----------
            is a complete and accurate list of all Matrix options issued and
            outstanding.

       (b)  Matrix is a corporation duly organized, validly existing and in good
            standing under the laws of the State of Texas with all requisite
            corporate power and authority to own, lease and operate its
            properties and to carry on its business as now being conducted.

       (c)  Matrix has full power and authority to enter into this Agreement and
            to carry out the transactions contemplated hereby, and this
            Agreement has been duly and validly executed and delivered by Matrix
            and constitutes the legal, valid and binding obligation of Matrix,
            enforceable in accordance with its terms. The execution, delivery
            and performance of this Agreement and all other transactions
            contemplated hereby will not cause any material default or breach in
            any contract, loan agreement or other instrument to which Matrix is
            a party or violate any law or decree or judgment of any government
            or governmental agency having jurisdiction over Matrix.

       (d)  Matrix's authorized capital stock consists of 10,000,000 shares of
            common stock, no par value, of which 3,484,260 shares are issued and
            outstanding. Schedule II is a list of all Matrix stock options
                         -----------                                      

                                      A-3

 
            existing as of the date hereof together with a list of all stock
            options that Matrix has agreed to issue but has not yet issued.

       (e)  The financial statements of Matrix listed on Schedule III fairly
                                                         ------------       
            present in all material respects Matrix's financial position and
            assets and its results of operation and changes in financial
            position with respect to the respective dates thereof and the
            periods covered thereby, in conformity with the United States
            generally accepted accounting principles at the time in effect
            ("GAAP"), and Matrix's past accounting practices, consistently
              ----
            applied during such periods, and such financial statements,
            including the notes thereto, make full and adequate disclosure of,
            and provision for, all of Matrix's material obligations and
            liabilities as of the date thereof, whether accrued, absolute,
            contingent or otherwise, to the extent required by GAAP. Since the
            date of the last of such financial statements, there have been no
            material adverse changes to the business or condition of Matrix that
            have not been disclosed to Avtel.

       (f)  Schedule IV contains a list of all material contracts between Matrix
            -----------                                                         
            and any of its officers, directors or shareholders, true, correct
            and complete copies of which have been furnished to Avtel.

       (g)  Schedule V contains a true, correct and complete list of all of
            ----------                                                     
            Matrix's employee benefit plans and a list of each employee of
            Matrix as of the date hereof, his/her current position, annual
            salary and current bonus entitlement.

       (h)  Except as set forth in Schedule VI, Matrix is not a party to and has
                                   -----------                                  
            not been threatened with any legal action, governmental
            investigation or proceeding or any other material claim or
            proceeding, including, without limitation, any tax audit.

       (i)  Matrix has provided Avtel copies of the prior three year's federal
            and state income tax returns and represents that it believes such
            returns fairly reflect Matrix's tax obligations for such periods and
            that no adjustments for such periods have been proposed. All
            federal, state, local and foreign tax returns required to be filed
            by or with respect to Matrix through the Closing Date have been or
            will be accurately prepared, and have been or will be duly and
            timely filed, and all taxes, interest, penalties, assessments and/or
            deficiencies due with respect to any taxable period ending on or
            before the Closing Date have been or will be timely paid, or
            adequate provision for the payment thereof has been or will be made
            on Matrix's financial statements or books of account.

       (j)  Except as disclosed on Schedule VII, no notice to, filing with,
                                   ------------                            
            authorization of, exemption by, or consent of any person, entity or
            public or governmental authority is required in order for Matrix to
            consummate the transactions contemplated hereby.

14.    AVTEL REPRESENTATIONS

       Avtel represents to Matrix as follows:

       (a)  Avtel is a corporation duly organized, validly existing and in good
            standing under the laws of the State of Utah with all requisite
            corporate power and authority to own, lease and operate its
            properties and to carry on its business as now being conducted.

       (b)  Avtel has full power and authority to enter into this Agreement and
            to carry out the transactions contemplated hereby, and this
            Agreement has been duly and validly executed and delivered by Avtel,
            and constitutes the legal, valid and binding obligation of Avtel,
            enforceable in accordance with its terms. The execution, delivery
            and performance of this Agreement and all other transactions
            contemplated hereby will not cause any material default or breach in
            any contract, loan agreement or other instrument to which Avtel is a
            party or violate any law or decree or judgement of any government or
            governmental agency having jurisdiction over Avtel.

       (c)  Avtel's authorized capital stock consists of 50,000,000 shares of
            common stock, $.001 par value, per share, of which 7,135,807 shares
            are issued and outstanding and 5,000,000 shares of preferred stock
            of which 1,000,000 shares designated, $1.00 par value Series A
            Convertible Preferred Stock are issued and outstanding. All such
            shares were held as of April 9, 1997 as set forth on Schedule VIII.
                                                                 -------------
            All of the issued shares of the capital stock of Avtel have been
            duly and validly authorized and issued, are fully paid and non-
            assessable. The shares of common stock to be delivered by Avtel to

                                      A-4

 
            the Stockholders pursuant to this Agreement have been duly and
            validly authorized and, when issued and delivered as provided
            herein, will be duly and validly issued and fully paid and non-
            assessable. Schedule IX is a list of all Avtel stock options
                        -----------
            existing as of the date hereof, together with a list of all stock
            options Avtel has agreed to issue but has not yet issued, and Avtel
            has not entered into any agreement to issue additional stock options
            except as disclosed on Schedule IX.
                                   -----------

       (d)  The financial statements of Avtel listed on Schedule X fairly 
                                                        ---------- 
            present in all material respects Avtel's financial position and
            assets and its results of operation and changes in financial
            position with respect to the respective dates thereof and the
            periods covered thereby, in conformity with GAAP and Avtel's past
            accounting practices, consistently applied during such periods, and
            such financial statements, including the notes thereto, make full
            and adequate disclosure of, and provision for, all of Avtel's
            material obligations and liabilities as of the date thereof, whether
            accrued, absolute, contingent or otherwise, to the extent required
            by GAAP. Since the date of the last of such financial statements,
            there have been no material adverse changes to the business or
            condition of Avtel that have not been disclosed to Matrix.

       (e)  Schedule XI contains a list of all material contracts between Avtel
            -----------        
            and any of its officers, directors or shareholders, true, correct
            and complete copies of which have been furnished to Matrix.

       (f)  Schedule XII contains a true, correct and complete list of all of
            ------------                                                     
            Avtel's employee benefit plans and a list of each employee of Avtel
            and its subsidiaries as of the date hereof, his/her current
            position, annual salary (and proposed adjustments thereto for the
            next 6 months) and current bonus entitlement.

       (g)  Except as set forth in Schedule XIII, Avtel is not a party to and 
                                   -------------                             
            has not been threatened with any legal action, governmental
            investigation or proceeding or any other material claim or
            proceeding, including, without limitation, any tax audit.

       (h)  Avtel has provided Matrix copies of the prior three year's federal
            and state income tax returns and represents that it believes such
            returns fairly reflect Avtel's tax obligations for such periods and
            that no adjustments for such periods have been proposed. All
            federal, state, local and foreign tax returns required to be filed
            by or with respect to Avtel from January 1, 1993 through the Closing
            Date have been or will be accurately prepared, and have been or will
            be duly and timely filed, and all taxes, interest, penalties,
            assessments and/or deficiencies due with respect to any taxable
            period ending on or before the Closing Date have been or will be
            timely paid, or adequate provision for the payment thereof has been
            or will be made on Avtel's financial statements or books of account.

       (i)  Except as disclosed on Schedule XIV, no notice to, filing with,
                                   ------------                            
            authorization of, exemption by, or consent of any person, entity or
            public or governmental authority is required in order for Avtel to
            consummate the transactions contemplated hereby.

15.    CONDITIONS PRECEDENT TO OBLIGATIONS OF MATRIX

       (a)  Avtel's representations and warranties contained herein shall be
            true in all material respects on and as of the date of this
            Agreement and shall also be true in all material respects (except
            for such changes as are contemplated by the terms of this Agreement)
            on and as of the Closing Date with the same force and effect as
            though made by Avtel on and as of the Closing Date.

       (b)  Avtel shall, in all material respects, have performed all
            obligations and agreements and complied with all covenants contained
            in this Agreement, to be performed and complied with by it on or
            prior to the Closing Date; and Avtel shall have delivered to Matrix
            a certificate, dated as of the Closing Date, certifying as to its
            compliance with Section 15(a) and Section 15(b).
                            -------------     -------------  

       (c)  The Registration Rights Agreement shall have been executed by the
            Avtel and delivered to Matrix.

       (d)  The shareholders of Avtel shall have approved this Agreement and the
            transactions contemplated hereby.

       (e)  Any and all governmental and other consents required in connection
            with this Agreement shall have been obtained.

                                      A-5

 
       (f)  Each Stockholder shall have executed an Exchange Statement.


16.    CONDITIONS PRECEDENT TO OBLIGATIONS OF AVTEL

       (a)  Matrix's representations and warranties contained herein shall be
            true in all material respects on and as of the date of this
            Agreement and shall also be true in all material respects (except
            for such changes as are contemplated by the terms of this Agreement)
            on and as of the Closing Date with the same force and effect as
            though made by Matrix on and as of the Closing Date.

       (b)  Matrix shall, in all material respects, have performed all
            obligations and agreements and complied with all covenants contained
            in this Agreement to be performed and complied with by it on or
            prior to the Closing Date and Matrix shall have delivered to Avtel a
            certificate, dated as of the Closing Date, certifying as to its
            compliance with Section 16(a) and Section 16(b).
                            -------------     -------------                

       (c)  The Registration Rights Agreement shall have been executed by Matrix
            and the Exchange Statements shall have ben executed by the
            Stockholders and such documents shall have been delivered to Avtel.

       (d)  The shareholders of Avtel shall have approved this Agreement and the
            transactions contemplated hereby.

       (e)  Any and all governmental consents required in connection with this
            Agreement shall have been obtained.

17.    CLOSING

       The Closing (the "Closing") shall take place at such place as Matrix and
                         -------                                               
       Avtel shall agree on the date that is three business days after the
       conditions referred to in clauses (d) and (e) of paragraphs 15 and 16
                                 -----------     ---    -------------     --
       shall have been obtained or on such later date to which the parties
       hereto otherwise shall agree (such date being the "Closing Date").
                                                          ------------   

18.    SURVIVAL

       The covenants, agreements, representations or warranties of the parties
       hereto contained in this Agreement or in any certificate or other writing
       delivered pursuant to, or in connection with, this Agreement shall
       survive one year from the Closing Date.

19.    TERMINATION

       This Agreement may be terminated at any time on or prior to the Closing
       Date:(i) with the mutual consent of Avtel and Matrix or (ii) by Avtel or
       Matrix, if the Closing shall not have taken place on or before July 1,
       1997, or such later date as may be mutually approved in writing by Avtel
       or Matrix.  This Agreement shall terminate automatically if the
       shareholders of Avtel do not approve this Agreement or any of the
       transactions contemplated hereby.

20.    MISCELLANEOUS

       (a)  This Agreement shall be governed by the laws of the State of Texas,
            without regard to the conflict of law rules of such state.

       (b)  This Agreement may be amended, modified or supplemented but only in
            writing signed by all of the parties hereto.

       (c)  All notices, requests, demands and other communications required or
            permitted hereunder shall be in writing and shall be deemed to have
            been duly given when delivered by hand, or by confirmed facsimile
            transmission, or on two business days following delivery to a
            commercial overnight air courier service, or five days after being
            mailed, first class postage prepaid, return receipt requested.

                                      A-6

 
       If to Matrix, addressed as follows:

       5215 North O'Connor Blvd.
       Suite 300
       Irving, Texas 75039
       Attention: Ronald W. Howard
       Facsimile:  (972) 506-3266

       with a copy to:

       Mayer, Brown & Platt
       190 South LaSalle Street
       Chicago, Illinois 60603
       Attention: David A. Carpenter
       Facsimile:  (312) 701-7711

       If to Avtel, addressed as follows:

       130 Cremona Drive, Suite C
       Santa Barbara, California 93117
       Attention: Anthony Papa
       Facsimile:  (805) 685-9685
 
       with a copy to:

       Price, Postel & Parma LLP
       200 E. Carrillo Street, Suite 400
       Santa Barbara, California 93101
       Attention:  Raymond LeBlanc
       Facsimile:  (805) 882-9869

       or to such other individual or address as a party hereto may designate
       for itself by notice given as herein provided.

   (d) The failure of a party hereto at any time or times to require performance
       of any provision hereof shall in no manner affect its right at a later
       time to enforce the same. No waiver by a party of any condition or of any
       breach of any term, covenant, representation or warranty contained in
       this Agreement shall be effective unless in writing, and no waiver in any
       one or more instances shall be deemed to be a further or continuing
       waiver of any such condition or breach in other instances or a waiver of
       any other condition or breach of any other term, covenant, representation
       or warranty.

   (e) This Agreement may be executed simultaneously in counterparts, each of
       which shall be deemed an original, but all of which together shall
       constitute one and the same instrument.

   (f) The Stockholders shall be deemed to be third party beneficiaries of the
       rights of Matrix hereunder.

   IN WITNESS WHEREOF, the parties hereto have caused this Agreement to be
   executed on the date first above written by their duly authorized
   representatives.

                                      A-7

 
MATRIX TELECOM, INC.                        AVTEL COMMUNICATIONS, INC.
 
 
By:_____________________________            By:_____________________________
 
 
________________________________            ________________________________
          (Print Name)                               (Print Name)
 
Its:_____________________________          Its:_____________________________
          (duly authorized)                        (duly authorized)
 

                                      A-8

 
                                   EXHIBIT A

                           FORM OF EXCHANGE STATEMENT

   The undersigned understands that the common stock of AvTel Communications,
Inc. ("Avtel") to be issued to the undersigned as consideration for shares of
       -----                                                                 
common stock of Matrix Telecom, Inc. ("Matrix") pursuant to that certain Stock
                                       ------                                 
Exchange Agreement (the "Stock Exchange Agreement") entered into as of April 29,
                         ------------------------                               
1997 between Avtel and Matrix will not be registered under the Securities Act of
1933, as amended (the "1933 Act"), or any applicable state securities laws, but
                       --------                                                
rather is being issued pursuant to the "private placement" exemption from
registration provided by Section 4(2) under the 1933 Act and certain analogous
state exemptions.  In connection with the offer and sale of the Avtel shares to
the undersigned pursuant to the Stock Exchange Agreement, the undersigned hereby
represents and warrants as follows:

(a) The undersigned (i) has such knowledge and experience in financial and
business matters that the undersigned is capable of evaluating the merits and
risks of the prospective investment in Avtel shares and (ii) is capable of
assuming the risk of the loss of the entire investment in connection therewith.

(b) The undersigned is not purchasing the shares of Avtel pursuant to the Stock
Exchange Agreement as a result of any general solicitation or general
advertising, including advertisements, articles, notices or other communications
published in any newspaper, magazine or similar media or broadcast over radio or
television, or any seminar or meeting whose attendees have been invited by
general solicitation or general advertising.

(c) The Avtel shares being purchased by the undersigned are acquired for the
undersigned's own account for investment and not with a view toward subdivision,
resale or redistribution thereof in a manner prohibited under the 1933 Act or
under the securities laws of any state, and the undersigned does not presently
have any reason to anticipate any change in the undersigned's circumstances or
other particular occasion or event that would create a need to sell such shares.
The undersigned has no contract, undertaking, agreement, understanding or
arrangement with any person to sell, transfer or pledge to any person any part
or all of the Avtel shares the undersigned is purchasing or any interest
therein, and the undersigned has no present plans to enter into the same.

(d) The undersigned received the annual report on Form 10-K filed by Avtel with
respect to its most recently completed fiscal year (and the related proxy
statement for Avtel's 1997 Annual Stockholder's Meeting) and all other documents
filed by Avtel with the Securities Exchange Commission since the date of such
Annual Report. The undersigned has understood such materials and has had an
opportunity to ask questions and receive answers about the terms and conditions
of the offering and sale of Avtel stock under the Stock Exchange Agreement, and
has received all information that the undersigned has requested from Avtel
concerning Avtel and the transactions contemplated by the Stock Exchange
Agreement.

(e) The undersigned has not relied, in connection with this transaction, upon
any statements, representations, warranties or agreements other than those set
forth in the documents referred to in clause (d) above and the Stock Exchange
                                      ----------                             
Agreement.

(f) The undersigned understands that the shares of Avtel stock being purchased
by the undersigned pursuant to the Stock Exchange Agreement will bear the
following legend:

THESE SECURITIES HAVE NOT BEEN REGISTERED UNDER THE SECURITIES ACT OF 1933 OR
APPLICABLE STATE SECURITIES LAWS.  THESE SECURITIES MAY NOT BE TRANSFERRED
WITHOUT SUCH REGISTRATION EXCEPT PURSUANT TO TRANSACTIONS EXEMPT FROM THE
REGISTRATION REQUIREMENTS UNDER THE SECURITIES ACT OF 1933 AND APPLICABLE STATE
SECURITIES LAWS.  ANY REPRESENTATION TO THE CONTRARY IS A CRIMINAL OFFENSE.

(g) In connection with an intended exchange of the shares of Matrix common stock
held by the undersigned for shares of Avtel common stock, the undersigned hereby
directs that all Matrix shares held by the undersigned be exchanged at the
Closing (as defined in the Stock Exchange Agreement) for Avtel shares in the
manner contemplated by the Stock Exchange Agreement. The officers of Matrix are
hereby authorized to take all action on behalf of the undersigned and to act as
attorney-in-fact, with full power of substitution, for the undersigned in
connection with the consummation of the transactions contemplated

                                      A-9

 
by the Stock Exchange Agreement, including, without limitation, the execution of
the Registration Rights Agreement (as defined therein). All Avtel shares
received are to be registered in the same name as the Matrix shares held by the
undersigned.

(h) The undersigned hereby represents and warrants that the undersigned has full
power to direct the exchange of the Matrix shares as set forth above and that
the shares of Matrix common stock to be exchanged by the undersigned are free
and clear of any liens or encumbrances.

(i) The undersigned understands that a false statement herein may be a violation
of law and could result in a claim for damages against the undersigned.


                        Signature________________________________

                        Print Name______________________________

                        Date:___________________________________

                        No. of Matrix Shares Held:_________

                                      A-10

 
                                   EXHIBIT B

                     FORM OF REGISTRATION RIGHTS AGREEMENT


   THIS REGISTRATION RIGHTS AND LOCK-UP AGREEMENT (this "Agreement") is made and
   entered into as of __________, 1997, by and between Avtel Communications,
   Inc. (the "Company") and Matrix Telecom, Inc. ("Matrix") on behalf of the
   Persons listed on Schedule A attached hereto, including their successors,
   assigns and transferees (herein referred to collectively as the "Holders" and
   individually as a "Holder").

   WHEREAS, on the date hereof each Holder is or will become the owner of Common
   Stock (as defined below) of the Company in connection with that certain Stock
   Exchange Agreement, dated April 29, 1997 (the "Stock Exchange Agreement")
   between the Company and Matrix; and

   WHEREAS, in connection with the Stock Exchange Agreement, the Holders have
   agreed to enter into the Lock-Ups (as defined below) as provided in Section 2
   below; and

   WHEREAS, as a condition to the closing of the Stock Exchange Agreement, the
   Company has agreed to grant the Holders the registration rights provided for
   in Sections 3 and 4 below;

   NOW, THEREFORE, the parties hereto, in consideration of the foregoing, the
   mutual covenants and agreements hereinafter set forth, and other good and
   valuable consideration, the receipt and sufficiency of which are hereby
   acknowledged, agree as follows:

1. Definitions.
   ----------- 

   As used in this Agreement, the following capitalized defined terms shall have
   the following meanings:

   "Closing Price" of the Common Stock for any given day shall mean (i) if the
    -------------                                                             
   Common Stock is listed or admitted to trading on a national securities
   exchange, the reported last sale price of the Common Stock, regular way, on
   such day or, in case no such sale takes place on such day, the average of the
   reported closing bid and asked prices, regular way, on such national
   securities exchange on such day or (ii) if the Common Stock is not listed or
   admitted to trading on any national securities exchange but is quoted by the
   Nasdaq SmallCap Market or the Nasdaq National Market of the Nasdaq Stock
   Market, Inc. ("NASDAQ"), the last reported sales price per share, regular
   way, on such day or, in case no such sale takes place on such day, or the
   last reported sales price is not quoted by NASDAQ, the average of the
   reported closing bid and asked prices, regular way, on such day.

   "Common Stock" shall mean the Common Stock, par value $.01, per share, of the
    ------------                                                                
   Company.

   "Company" shall mean Avtel Communications, Inc., a Delaware Corporation, and
    -------                                                                    
   its successors.

   "Dispose of" shall have the meaning provided in Section 2(a).
    ----------                                                  

   "Exchange Act" shall mean the Securities Exchange Act of 1934, as amended
    ------------                                                            
   from time to time.

   "Holder" or "Holders" shall mean the persons listed on Schedule A attached
    ------      -------                                                      
   hereto, including their successors, assigns and transferees.

   "Lock-ups" shall mean the restrictions on transfer to which the Holders are
    --------                                                                  
   subject pursuant to Section 2(a).

   "Lock-up Period" shall mean the applicable time periods to which the Holders
    --------------                                                             
   have agreed to the Lock-ups.

   "Person" shall mean an individual, partnership, corporation, trust,
    ------                                                            
   unincorporated organization or other legal entity or a government or agency
   or political subdivision thereof.

   "Registrable Securities" shall mean the Shares, excluding (i) Shares that
    ----------------------                                                  
   have been disposed of under the Shelf Registration Statement or any other
   effective registration statement, (ii) Shares sold or otherwise transferred
   pursuant to Rule 144 under the Securities Act, (iii) Shares that are held by
   Holders who are not

                                      A-11

 
   affiliates of the Company that are or become eligible for sale pursuant to
   Rule 144(k) under the Securities Act, and (iv) Shares held by each Holder who
   is an affiliate of the Company if all of such Shares are or become eligible
   for sale pursuant to Rule 144 under the Securities Act and could be sold in
   one transaction in accordance with the volume limitations contained in Rule
   144(e)(1)(i) under the Securities Act.

   "Registration Expenses" shall mean any and all expenses incident to
    ---------------------                                             
   performance of or compliance with this Agreement, including, without
   limitation: (i) all applicable registration and filing fees imposed by the
   SEC, or the National Association of Securities Dealers, Inc. ("NASD"), (ii)
   all fees and expenses incurred in connection with compliance with state
   securities or "blue sky" laws (including reasonable fees and disbursements of
   counsel in connection with qualification of any of the Registrable Securities
   under any state securities or blue sky laws and the preparation of a blue sky
   memorandum) and compliance with the rules of the NASD, (iii) all expenses of
   any Persons in preparing or assisting in preparing, word processing, printing
   and distributing the Shelf Registration Statement, any Prospectus,
   certificates and other documents relating to the performance of and
   compliance with this Agreement, (iv) all fees and expenses incurred in
   connection with the listing, if any, of any of the Registrable Securities on
   any securities exchange or exchanges pursuant to Section 4(l) hereof, and (v)
   the fees and disbursements of counsel for the Company and of the independent
   public accountants of the Company, including the expenses of any special
   audits or "cold comfort" letters required by or incident to such performance
   and compliance. Registration Expenses shall specifically exclude underwriting
   discounts and commissions, the fees and disbursements of counsel representing
   a selling Holder or any underwriter or agent acting on behalf of a Holder,
   and transfer taxes, if any, relating to the sale or disposition of
   Registrable Securities by a selling Holder, all of which shall be borne by
   such Holder in all cases.

   "Registration Notice" shall have the meaning set forth in Section 4(b)
    -------------------                                                  
   hereof.

   "Registration Statement" shall mean a registration statement, including a
    ----------------------                                                  
   Shelf Registration Statement, of the Company that covers all of the
   Registrable Securities and all amendments (including post-effective
   amendments) to such registration statement, and all exhibits thereto and
   materials incorporated by reference therein.

   "SEC" shall mean the Securities and Exchange Commission.
    ---                                                    

   "Securities Act" shall mean the Securities Act of 1933, as amended from time
    --------------                                                             
   to time.

   "Shares" shall mean the Common Stock issued to the Holders pursuant to the
    ------                                                                   
   Stock Exchange Agreement.

   "Shelf Registration Statement" shall mean a Registration Statement covering
    ----------------------------                                              
   the Registrable Securities filed pursuant to Rule 415 under the Securities
   Act, or any similar rule established by the SEC.

   "Stock Exchange Agreement" shall have the meaning set forth in the recitals.
    ------------------------                                                   

2. Lock-up Agreement.
   ----------------- 

   (a)  Each of the Holders identified in Schedule B hereby agrees that, from
   the date hereof until two years following the closing of the sale of Common
   Stock to the Holder pursuant to the Stock Exchange Agreement, without the
   prior written consent of the Company, such Holder will not offer, pledge,
   sell, contract to sell, grant any options for the sale of or otherwise
   dispose of, directly or indirectly (collectively, "Dispose of"), any Shares.

   (b)  All other Holders hereby agree that, from the date hereof until the date
   on which the Company releases a press release announcing earnings on a
   consolidated basis, including the operations of Matrix, covering a period of
   combined earnings of not less than 30 days, without the prior written consent
   of the Company, such Holders will not Dispose of any Shares.

3. Shelf Registration Under the Securities Act.
   ------------------------------------------- 

   (a)  Filing of Shelf Registration Statement.  Following the date hereof, the
        --------------------------------------                                 
   Company shall use its best efforts to become listed on the Nasdaq SmallCap
   Market or the Nasdaq National Market of NASDAQ whereupon it shall file, a
   Shelf Registration Statement providing for the sale by the Holders of all of
   the Registrable Securities in accordance with the terms hereof and will use
   its reasonable efforts to cause such

                                      A-12

 
   Shelf Registration Statement to be declared effective by the SEC as soon
   thereafter as is practicable. The Company agrees to use its reasonable
   efforts to keep the Shelf Registration Statement with respect to the
   Registrable Securities continuously effective for a period expiring on the
   earlier of (i) the date on which all of the Registrable Securities covered by
   the Shelf Registration Statement have been sold pursuant thereto and (ii) the
   date on which (A) all Shares held by Holders who are not affiliates of the
   Company, in the opinion of counsel for the Company are eligible for sale
   pursuant to Rule 144(k) under the Securities Act and (B) all Shares held by
   each Holder who is an affiliate of the Company, in the opinion of counsel for
   the Company are eligible for sale pursuant to Rule 144 under the Securities
   Act and could be sold in one transaction in accordance with the volume
   limitations contained in Rule 144(e)(1)(i) under the Securities Act.

   (b)   Demand Rights.  Notwithstanding clause (a) above and subject to the
         -------------                                                      
   restrictions on disposition included in Section 2, if the Company is unable
   to become listed on the Nasdaq SmallCap Market or the Nasdaq National Market
   within six months of the date hereof, or is otherwise unable to qualify for
   use of a Shelf Registration Statement, on the date which is six months from
   the date hereof, the Company shall, upon receipt of a notice (a "Registration
   Notice") given at least 14 days prior to the six-month anniversary hereof,
   file on behalf of all Holders from whom it shall have received a Registration
   Notice, and use its best efforts to cause to become effective as soon as
   practical thereafter, a Registration Statement registering the offering and
   sale of the Registrable Securities which the Company has been requested to
   register by such Holders. In addition, subject to the restrictions on
   disposition included in Section 2 and on a maximum of two separate occasions
   (and if the Company at such time does not have an effective Shelf
   Registration Statement covering the Registerable Securities), at any time
   after the six month anniversary of the date hereof that the Company shall
   receive a Registration Notice from Holders holding Shares representing in
   excess of 25% of the Shares, it shall file, and use its best efforts to cause
   to become effective as soon as practical thereafter, a Registration Statement
   registering the offering and sale of the Registrable Securities held by such
   Holder (and those of any other Holder, subject to Section 2, who requests to
   have its Shares included in such Registration Statement). The Company shall
   promptly following receipt of a Registration Notice pursuant to the last
   sentence hereof notify the Holders of all other Registrable Securities and,
   upon request of such Holders, allow such Holders to include their Registrable
   Securities in the aforementioned Registration Statement. Notwithstanding the
   above, (i) if a request for registration pursuant to this Section 2(b) is
   made within 30 days prior to the conclusion of the Company's fiscal year, or
   within 40 days after the end of the Company's fiscal year, the Company shall
   not be required to file a registration statement until such time as the
   Company receives its audited financial statements for such fiscal year, and
   (ii) the Company shall be entitled to postpone for a reasonable period of
   time (not to exceed 90 days, which may not thereafter be extended) the filing
   of any registration statement otherwise required to be prepared and filed by
   it pursuant to this Section 2(b) if (x) the Company is in possession of
   material information that has not been disclosed to the public and the
   Company deems it advisable not to disclose such information in the
   registration statement or (y) the board of directors of the Company shall
   determine in good faith that such offering will interfere with a pending or
   contemplated financing, merger, acquisition, sale of assets, recapitalization
   or other similar corporate action of the Company, and in the case of clause
   (x) or (y) above, the Company shall have furnished to the Holder or Holders
   of Registrable Securities requesting such registration an officers'
   certificate to that effect.

   (c)   Expenses.  The Company shall pay all Registration Expenses in
         --------                                                     
   connection with the registration pursuant to Sections 3(a) or 3(b). The
   Company shall not be liable for any underwriting discounts and commissions,
   the fees and disbursements of counsel representing such Holder or any
   underwriter or agent acting on behalf of a Holder, and transfer taxes, if
   any, relating to the sale or disposition of such Holder's Registrable
   Securities pursuant to the Registration Statement or Rule 144 under the
   Securities Act.

   (d)   Inclusion in Registration Statement.  Any Holder who does not provide
         -----------------------------------                                  
   the information reasonably requested by the Company in connection with any
   Registration Statement filed hereunder by the Company as promptly as
   practicable after receipt of such request, but in no event later than ten
   (10) days thereafter, shall not be entitled to have its Registrable
   Securities included in any Registration Statement filed by the Company
   pursuant to this Agreement.

4. Registration Procedures.
   ----------------------- 

   In connection with the obligations of the Company with respect to the
   Registration Statements contemplated by Section 3 hereof, the Company shall:

                                      A-13

 
   (a)  prepare and file with the SEC, within the time period set forth in
   Section 3 hereof, the Registration Statements, which Registration Statements
   shall (i) be available for the sale of the Registrable Securities in
   accordance with the intended method or methods of distribution by the selling
   Holders thereof and (ii) comply as to form in all material respects with the
   requirements of the applicable form and include all financial statements
   required by the SEC to be filed therewith;
   
   (b)  furnish to each Holder of Registrable Securities that has delivered a
   Registration Notice to the Company or otherwise is entitled to have its
   Registrable Securities included in a Registration Statement, without charge,
   as many copies of each Prospectus and any amendment or supplement thereto in
   order to facilitate the public sale or other disposition of the Registrable
   Securities; the Company consents to the use of the Prospectus and any
   amendment or supplement thereto by each such Holder of Registrable Securities
   in connection with the offering and sale of the Registrable Securities
   covered by the Prospectus or amendment or supplement thereto;

   (c)  use its reasonable efforts to register or qualify the Registrable
   Securities by the time any Registration Statement is declared effective by
   the SEC under all applicable state securities or blue sky laws of such
   jurisdictions in the United States and its territories and possessions as any
   Holder of Registrable Securities covered by the Registration Statement shall
   reasonably request in writing, keep each such registration or qualification
   effective during the period such Registration Statement is required to be
   kept effective or during the period offers or sales are being made by a
   Holder that has delivered a Registration Notice to the Company, whichever is
   shorter; provided, however, that in connection therewith, the Company shall
            --------  -------
   not be required to (i) qualify as a foreign corporation to do business or to
   register as a broker or dealer in any such jurisdiction where it would not
   otherwise be required to qualify or register but for this Section 4(c), (ii)
   subject itself to taxation in any such jurisdiction, or (iii) file a general
   consent to service of process in any such jurisdiction;

   (d)  furnish to each Holder of Registrable Securities that has delivered a
   Registration Notice to the Company or is otherwise entitled to have its
   Registrable Securities included in a Registration Statement, without charge,
   at least one conformed copy of the Registration Statement and any post-
   effective amendment thereto (without documents incorporated therein by
   reference or exhibits thereto, unless requested);

   (e)  cooperate with the selling Holders of Registrable Securities to
   facilitate the timely preparation and delivery of certificates representing
   Registrable Securities to be sold and not bearing any Securities Act legend;
   and enable certificates for such Registrable Securities to be issued for such
   numbers of shares and registered in such names as the selling Holders may
   reasonably request at least two business days prior to any sale of
   Registrable Securities;

   (f)  make available for inspection by the Holders of Registrable Securities
   that have provided a Registration Notice to the Company and any counsel,
   accountants or other representatives retained by such Holders all financial
   and other records, pertinent corporate documents and properties of the
   Company and cause the officers, directors and employees of the Company to
   supply all such records, documents or information reasonably requested by
   such Holders, counsel, accountants or representatives in connection with the
   Registration Statement; provided, however, that such records, documents or
                           --------  -------
   information which the Company determines in good faith to be confidential and
   notifies such Holders, counsel, accountants or representatives in writing
   that such records, documents or information are confidential shall not be
   disclosed by such Holders, counsel, accountants or representatives unless (i)
   such disclosure is ordered pursuant to a subpoena or other order from a court
   of competent jurisdiction, or (ii) such records, documents or information
   become generally available to the public other than through a breach of this
   Agreement;

   (g)  use its reasonable efforts to cause all Registrable Securities to be
   listed on any securities exchange or automated quotation or other trading
   system on which similar securities issued by the Company are then listed or
   traded;

   The Company may require each Holder of Registrable Securities to furnish to
   the Company in writing such information regarding the proposed distribution
   by such Holder of such Registrable Securities as the Company may from time to
   time reasonably request in writing.

5. Repurchase by Company of Shares Subject to Registration Notice.  Upon receipt
   --------------------------------------------------------------               
   by the Company of a Registration Notice, the Company may, but shall not be
   obligated to, purchase from such Holder all, but

                                      A-14

 
   not less than all, of the Shares which are the subject of such Registration
   Notice at a price per share equal to the average of the Closing Prices of the
   Common Stock for the twenty trading days immediately preceding the date of
   the Registration Notice. In the event the Company elects to purchase the
   Shares which are the subject of a Registration Notice, the Company shall
   notify the Holder of such Shares within five business days of the date of
   receipt of the Registration Notice by the Company, which notice shall
   indicate: (i) that the Company will purchase the Shares which are the subject
   of the Registration Notice, (ii) the price per share, calculated in
   accordance with the preceding sentence, which the Company will pay to such
   Holder and (iii) the date upon which the Company shall repurchase such
   Shares, which date shall not be later than the tenth business day after
   receipt of the Registration Notice relating to such Shares.

6. Indemnification.
   --------------- 

   (a)  Indemnification by the Company.  The Company agrees to indemnify and 
        ------------------------------    
   hold harmless each Holder and its officers and directors and each Person, if
   any, who controls any Holder within the meaning of Section 15 of the
   Securities Act as follows:

        (i)  against any and all loss, liability, claim, damage and expense
   whatsoever, as incurred, to which such Holder, officer, director or
   controlling Person may become subject under the Securities Act or otherwise
   (A) that arise out of or are based upon any untrue statement or alleged
   untrue statement of a material fact contained in any Registration Statement
   or any amendment thereto, or the omission or alleged omission to state
   therein a material fact required to be stated therein or necessary to make
   the statements therein not misleading or (B) that arise out of or are based
   upon any untrue statement or alleged untrue statement of a material fact
   contained in any Prospectus or any amendment or supplement thereto, or the
   omission or alleged omission to state therein a material fact necessary in
   order to make the statements therein, in the light of the circumstances under
   which they were made, not misleading;

        (ii)  against any and all loss, liability, claim, damage and expense
   whatsoever, as incurred, to the extent of the aggregate amount paid in
   settlement of any litigation, or investigation or proceeding by any
   governmental agency or body, commenced or threatened, or of any claim
   whatsoever based upon any such untrue statement or alleged untrue statement
   or any omission or alleged omission, if such settlement is effected with the
   written consent of the Company; and

        (iii)  against any and all expense whatsoever, as incurred (including
   reasonable fees and disbursements of counsel), reasonably incurred in
   investigating, preparing or defending against any litigation, or
   investigation or proceeding by any governmental agency or body, commenced or
   threatened, in each case whether or not a party, or any claim whatsoever
   based upon any such untrue statement or alleged untrue statement or omission
   or alleged omission, to the extent that any such expense is not paid under
   subparagraph (i) or (ii) above;

provided, however, that the indemnity provided pursuant to this Section 6(a)
- --------  -------                                                           
   shall not apply to any Holder with respect to any loss, liability, claim,
   damage or expense that arise out of or are based upon any untrue statement or
   alleged untrue statement or omission or alleged omission made in reliance
   upon and in conformity with written information furnished to the Company by
   such Holder expressly for use in a Registration Statement or any amendment
   thereto or the Prospectus or any amendment or supplement thereto.

   (b)  Indemnification by Holders.  Each Holder severally agrees to indemnify
        --------------------------                                            
   and hold harmless the Company and the other selling Holders, and each of
   their respective directors and officers (including each director and officer
   of the Company who signed the Registration Statement), and each Person, if
   any, who controls the Company or any other selling Holder within the meaning
   of Section 15 of the Securities Act, to the same extent as the indemnity
   contained in Section 6(a) hereof, but only insofar as such loss, liability,
   claim, damage or expense arises out of or is based upon any untrue statement
   or alleged untrue statement or omission or alleged omission made in the Shelf
   Registration Statement or any amendment thereto or the Prospectus or any
   amendment or supplement thereto in reliance upon and in conformity with
   written information furnished to the Company by such selling Holder expressly
   for use therein.

   (c)  Indemnification Proceedings.  Any Person entitled to indemnification
        ---------------------------                                         
   hereunder will (i) give prompt notice to the indemnifying party of any claim
   with respect to which it seeks indemnification and (ii) permit such
   indemnifying party to assume the defense of such claim with counsel
   reasonably satisfactory to the indemnified party; provided, however, that any
   Person entitled to indemnification hereunder shall have the

                                      A-15

 
   right to employ separate counsel and to participate in the defense of such
   claim, but the fees and expenses of such counsel shall be at the expense of
   such Person and not of the indemnifying party unless (x) the indemnifying
   party has agreed to pay such fees or expenses, or (y) the indemnifying party
   shall have failed to assume the defense of such claim or employ counsel
   reasonably satisfactory to such Person, or (z) in the reasonable judgment of
   the Person to be indemnified, a conflict of interest may exist between such
   Person and the indemnifying party with respect to such claims (in which case,
   if the Person notifies the indemnifying party in writing that such Person
   elects to employ separate counsel at the expense of the indemnifying party,
   the indemnifying party shall not have the right to assume the defense of such
   claim on behalf of such Person). If such defense is not assumed by the
   indemnifying party, the indemnifying party will not be subject to any
   liability for any settlement made without its consent (but such consent will
   not be unreasonably withheld). No indemnified party will be required to
   consent to entry of any judgement or enter into any settlement which does not
   include as an unconditional term thereof the giving by all claimants or
   plaintiffs to such indemnified party of a release from all liability in
   respect to such claim.

7. Rule 144 Sales.
   -------------- 

   (a)  Compliance.  The Company covenants that, so long as it is subject to the
        ----------                                                              
   reporting requirements of the Exchange Act, it will file the reports required
   to be filed by it under the Exchange Act so as to enable any Holder to sell
   Registrable Securities pursuant to Rule 144 under the Securities Act.

   (b)  Cooperation with Holders.  In connection with any sale, transfer or
        ------------------------                                           
   other disposition by any Holder of any Registrable Securities pursuant to
   Rule 144 under the Securities Act, the Company shall cooperate with such
   Holder to facilitate the timely preparation and delivery of certificates
   representing Registrable Securities to be sold and not bearing any Securities
   Act legend, and enable certificates for such Registrable Securities to be for
   such number of shares and registered in such names as the selling Holders may
   reasonably request at least two business days prior to any sale of
   Registrable Securities. The Company's obligation set forth in the previous
   sentence shall be subject to the delivery, if reasonably requested by the
   Company or its transfer agent, by counsel to such Holder, in form and
   substance reasonably satisfactory to the Company and its transfer agent, of
   an opinion that such Securities Act legend need not appear on such
   certificate.

8. Miscellaneous.
   ------------- 

   (a)  Amendments and Waivers.  The provisions of this Agreement, including
        ----------------------                                              
   the provisions of this sentence, may not be amended, modified, supplemented
   or waived, nor may consent to departures therefrom be given, without the
   written consent of the Company and the Holders of a majority of the
   outstanding Registrable Securities. Notice of any such amendment,
   modification, supplement, waiver or consent adopted in accordance with this
   Section 8(a) shall be provided by the Company to each Holder of Registrable
   Securities at least thirty (30) days prior to the effective date of such
   amendment, modification, supplement, waiver or consent.

   (b)  Notices.  All notices and other communications provided for or
        -------                                                       
   permitted hereunder shall be made in writing by hand-delivery, registered
   first-class mail, telex, telecopier, or any courier guaranteeing overnight
   delivery, (i) if to a Holder, at such Holder's registered address appearing
   on the share register of the Company or (ii) if to the Company, at its
   corporate headquarters, Attention: President.

        All such notices and communications shall be deemed to have been duly
   given: at the time delivered by hand, if personally delivered; five business
   days after being deposited in the mail, postage prepaid, if mailed; when
   answered back, if telexed; when receipt is acknowledged, if telecopied; or at
   the time delivered if delivered by an air courier guaranteeing overnight
   delivery.

   (c)  Successors and Assigns.  This Agreement shall inure to the benefit of
        ----------------------                                               
   and be binding upon the successors, assigns and transferees of each of the
   parties, including, without limitation and without the need for an express
   assignment, subsequent Holders.

   (d)  Counterparts.  This Agreement may be executed in any number of
        ------------                                                  
   counterparts and by the parties hereto in separate 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.

                                      A-16

 
   (e)  Governing Law.  This Agreement shall be governed by and
        -------------                                          
   construed in accordance with the laws of the State of Delaware without giving
   effect to the conflicts of law provisions thereof.


   IN WITNESS WHEREOF, the parties have executed this Agreement as of the date
first written above

                                       AVTEL COMMUNICATIONS, INC.


                                       By:____________________________
                                       Name:__________________________
                                       Title:_________________________


                                       MATRIX TELECOM, INC.
                                       On behalf of all Holders


                                       By:____________________________
                                       Name:__________________________
                                       Title:_________________________

                                      A-17

 
                                   Schedule A
                                   ----------


                                    HOLDERS

                                BestConnections
                                      UGA
                                  James Jensen
                                  Jami Jensen
                                  Jeff Jensen
                                  Janet Jensen
                                  Julie Jensen
                                    UA Plus
                                Howard Neckowitz
                                   Ron Jensen
                                   Ray Waters
                                 Gary Friedman
                                 E. Scott Crist
                                  Gail Granton
                                  Chuck Taylor
                                  Ron Anderson
                                  Joe Renteria
                                 Virginia Baker
                                   Tom Cargal
                                   Greg Reid
                              Greg Reid (in Trust)
                                  Cole Dawson
                                 Vernon Woelke

                                      A-18

 
                                   Schedule B
                                   ----------


                     Holders Subject to a Two Year Lock-up

                                      UGA
                                Ronald L. Jensen
                                  James Jensen
                                  Jami Jensen
                                  Jeff Jensen
                                  Janet Jensen
                                  Julie Jensen
                                    UA Plus

                                      A-19

 
                     AMENDMENT TO STOCK EXCHANGE AGREEMENT
                     -------------------------------------


This Amendment to Stock Exchange Agreement, dated August 25, 1997 is by and
between Matrix Telecom, Inc. ("Matrix") and AvTel Communications, Inc.
("AvTel").

                              W I T N E S S E T H
                              -------------------

WHEREAS, Matrix and AvTel have entered into that certain Stock Exchange
Agreement, dated April 29, 1997 (the "Stock Exchange Agreement") which provided
for, among other things, the exchange by the stockholders of Matrix of all of
the issued and outstanding capital stock and options of Matrix for capital stock
and options of AvTel;

WHEREAS, by letter agreement, dated July 28, 1997 (the "Letter Agreement") the
date by which completion of the transactions by the Stock Exchange Agreement is
required to be completed was extended through November 30, 1997; and

WHEREAS, as contemplated by Paragraph 9(b) of the Stock Exchange Agreement,
                            --------------
AvTel and Matrix have agreed to effect the Reverse Stock Split (as defined in
the Stock Exchange Agreement) by the conversion of each share of AvTel common
stock into the right to receive 1/4 of a share of common stock of Newco (thereby
effecting a four to one reverse stock split) pursuant to the terms of the Merger
(as defined in the Stock Exchange Agreement);

WHEREAS, since the date of the Stock Exchange Agreement, Matrix has acquired all
of the issued and outstanding capital stock of Best Connections, Inc. in
exchange for 376,727 shares of Matrix common stock;

NOW THEREFORE, in consideration of the foregoing and for other good and valuable
consideration, the receipt and sufficiency of which are hereby acknowledged, the
parties agree as follows:

9.  Defined Terms. Capitalized terms used herein, unless otherwise defined or
    -------------
the context requires otherwise, are used herein as defined in the Stock Exchange
Agreement.

10. Amendment to Paragraph 1.  Paragraph 1 of the Stock Exchange Agreement is
    ------------------------   -----------                                
hereby amended to read in its entirety as follows:

    "At Closing (as hereinafter defined), the stockholders of Matrix listed on
Schedule I (the "Stockholders") will deliver to AvTel 3,860,987 properly
- ----------
endorsed, unencumbered shares of Matrix common stock, representing 100% of the
outstanding Matrix common stock, in exchange for 9,582,514 shares of common
stock of AvTel, after giving effect to the Merger and Reverse Stock Split
(defined below), which will not be registered under the Securities Act of 1933,
as amended."

11.  Amendment to Paragraph 2.  Paragraph 2 of the Stock Exchange Agreement is
     ------------------------   -----------                                
hereby amended by adding the following sentence at the end of the paragraph:

    "Prior to the Closing, Matrix shall deliver to AvTel a duly executed
Exchange Statement from each holder of a non-qualified stock option of Matrix in
the form attached as Exhibit B."
                     ---------  

12.  Amendment to Paragraph 3.  Paragraph 3 of the Stock Exchange Agreement is
     ------------------------   -----------                                
hereby amended to read in its entirety as follows:

    "At Closing, Matrix will cancel all non-qualified stock options (covering
9,000 Matrix shares) that it has granted and that remain outstanding as of the
date hereof, and AvTel will issue to the beneficiaries thereof, 22, 338 AvTel
non-qualified stock options, after giving effect to the Merger and Reverse Stock
Split, having the exercise period and exercise price set forth in Exhibit B
                                                                  ---------
hereto."

13.  Amendment to Paragraph 6.  Paragraph 6 of the Stock Exchange Agreement, 
     ------------------------   -----------                      
including the heading thereto, is hereby deleted and replaced entirely by the
following:

                           "[INTENTIONALLY OMITTED.]"

                                      A-20

 
14.  Amendment to Paragraph 9(a).  The last sentence of Paragraph 9(a) of the
     ---------------------------                        --------------   
Stock Exchange Agreement is hereby amended to read in its entirety as follows:

     "At the effective time of the Merger, by virtue of the Merger, and without
any action on the part of AvTel or Newco or the stockholders of Newco, each
share of common stock and preferred stock, and each option of AvTel issued and
outstanding immediately prior to the effective time of the Merger shall by
virtue of the Merger be canceled and extinguished and be converted into the
right to receive one quarter of a share of common stock or preferred stock or an
option to acquire one quarter of a share of common stock, as applicable, of
Newco; provided, however, that Newco shall not be required to issue any
       --------  -------
fractional shares of common stock or preferred stock but instead shall be
entitled to purchase any fractional shares resulting from the Merger at the fair
market value thereof. This 1/4 to 1 conversion of shares is referred to herein
as the "Reverse Stock Split."

15.  Amendment to Paragraph 9(b).  Paragraph 9(b) of the Stock Exchange 
     ---------------------------   --------------                      
Agreement shall be deleted in its entirety.

16.  Amendments to Paragraph 12.
     -------------------------- 

     (a) The $500,000 amount set forth in the first sentence of Paragraph 12 is
                                                                ------------
hereby deleted and replaced with $750,000.

     (b) The following clause is hereby inserted after clause (b) of Paragraph
                                                       ----------    ---------
12 and clauses (c), (d) and (e) of Paragraph 12 are hereby renumbered to be
- --     ----------   ---     ---    ------------
clauses (d), (e) and (f), respectively:
- -----------  ---     ---

     "(c) up to an additional $250,000 may be drawn by AvTel at any time on or
after July 1, 1997 and prior to the earlier of (i) September 30, 1997, or (ii)
the termination of this Agreement."

     (c) The date "August 31, 1997" set forth in the first sentence of clause
                                                                       ------
(d) of Paragraph 12 of the Stock Exchange Agreement (which after giving effect
- ---    ------------
to this Amendment will become clause (e)) is hereby deleted and replaced with
                              ----------
the date "October 31, 1997."

17.  Amendment to Paragraph 15.   Clause (f) of Paragraph 15 of the Stock
     -------------------------    ----------    ------------             
Exchange Agreement is hereby amended to read in its entirety as follows:

     "Stockholders holding at least 90% of the issued and outstanding common
stock of Matrix shall have executed and delivered to Matrix an Exchange
Statement."

18.  Amendment to Paragraph 19.  The date "July 1, 1997" set forth in the first
     -------------------------                                           
sentence of Paragraph 19 is hereby deleted and replaced with the date "November
            ------------
30, 1997", consistent with the terms of the Letter Agreement.

19.  Amendment to Schedules. Schedules I, II, and VII of the Stock Exchange
     ----------------------  -----------  --      ---
Agreement are hereby deleted and replaced with Schedules I, II, and VII attached
                                               -----------  --      ---
hereto.

20.  Amendment to Registration Rights Agreement.  The Registration Rights
     ------------------------------------------                          
Agreement included as Exhibit B to the Stock Exchange Agreement (Exhibit C after
                      ---------                                  ---------      
giving effect to this Agreement) is hereby amended by deleting Section 2(b)
thereof.

21.  Amendment to Exhibits.  Any references in the Stock Exchange Agreement to
     ---------------------                                                 
Exhibit B are hereby amended to refer to Exhibit C to the Stock Exchange 
- ---------                                ---------                      
Agreement and the Registration Rights Agreement previously included as Exhibit B
                                                                       ---------
to the Stock Exchange Agreement is hereby amended to become Exhibit C thereto.
                                                            ---------          
Exhibit B to the Stock Exchange Agreement shall read entirely as set forth in
- ---------                                                                    
Exhibit B attached hereto.
- ---------                 

22.  Effectiveness of Amendment.  This Amendment shall become effective upon
     --------------------------                                        
the execution hereof by each of the parties hereto. Except as amended hereby,
the Stock Exchange Agreement shall remain in full force and effect.

23.  Counterparts.  This Amendment may be executed simultaneously in 
     ------------                                                   
counterparts, each of which shall be deemed to be an original, but all of which
together shall constitute one and the same instrument.

                                      A-21

 
     IN WITNESS WHEREOF, the parties have caused this Amendment to be executed
     on the dated first above written by their duly authorized representatives.



MATRIX TELECOM, INC.                      AVTEL COMMUNICATIONS, INC.



By:____________________                   By:___________________________
Title:_________________                   Title:________________________

                                      A-22

 
                                   EXHIBIT B

                       FORM OF OPTION EXCHANGE STATEMENT

The undersigned understands that the option or options to acquire common stock 
of AvTel Communications, Inc. ("Avtel") to be issued to the undersigned as
                                      -----                                     
consideration for options to acquire shares of common stock of Matrix Telecom,
Inc. ("Matrix") pursuant to that certain Stock Exchange Agreement (the "Stock
       ------                                                           -----
Exchange Agreement") entered into as of April 29, 1997 between Avtel and Matrix
- ------------------                                                             
will not be registered under the Securities Act of 1933, as amended (the "1933
                                                                          ----
Act"), or any applicable state securities laws, but rather are being issued
- ---                                                                        
pursuant to the "private placement" exemption from registration provided by
Section 4(2) under the 1933 Act and certain analogous state exemptions.  In
connection with the offer and sale of the Avtel options to the undersigned
pursuant to the Stock Exchange Agreement, the undersigned hereby represents and
warrants as follows:

(a)  The undersigned (i) has such knowledge and experience in financial and
business matters that the undersigned is capable of evaluating the merits and
risks of the prospective investment in Avtel options and the resulting Avtel
shares to be issued upon the exercise of the options and (ii) is capable of
assuming the risk of the loss of the entire investment in connection therewith.

(b)  The undersigned is not acquiring the Avtel options pursuant to the
Stock Exchange Agreement as a result of any general solicitation or general
advertising, including advertisements, articles, notices or other communications
published in any newspaper, magazine or similar media or broadcast over radio or
television, or any seminar or meeting whose attendees have been invited by
general solicitation or general advertising.

(c)  The Avtel options being acquired by the undersigned are acquired for
the undersigned's own account for investment and not with a view toward
subdivision, resale or redistribution thereof in a manner prohibited under the
1933 Act or under the securities laws of any state, and the undersigned does not
presently have any reason to anticipate any change in the undersigned's
circumstances or other particular occasion or event that would create a need to
sell such options.  The undersigned has no contract, undertaking, agreement,
understanding or arrangement with any person to sell, transfer or pledge to any
person any part or all of the Avtel options the undersigned is acquiring or any
interest therein, and the undersigned has no present plans to enter into the
same.

(d)  The undersigned received the annual report on Form 10-K filed by Avtel
with respect to its most recently completed fiscal year (and the related proxy
statement for Avtel's 1997 Annual Stockholder's Meeting) and all other documents
filed by Avtel with the Securities Exchange Commission since the date of such
Annual Report.  The undersigned has understood such materials and has had an
opportunity to ask questions and receive answers about the terms and conditions
of the offering and the issuance of Avtel options under the Stock Exchange
Agreement, and has received all information that the undersigned has requested
from Avtel concerning Avtel and the transactions contemplated by the Stock
Exchange Agreement.

(e)  The undersigned has not relied, in connection with this transaction,
upon any statements, representations, warranties or agreements other than those
set forth in the documents referred to in clause (d) above and the Stock
                                          ----------                    
Exchange Agreement.

(f)  In connection with an intended exchange of the options to acquire shares of
Matrix common stock held by the undersigned for options to acquire shares of
Avtel common stock, the undersigned hereby directs that all Matrix options held
by the undersigned be exchanged at the Closing (as defined in the Stock Exchange
Agreement) for Avtel options in the manner contemplated by the Stock Exchange
Agreement. The officers of Matrix are hereby authorized to take all action on
behalf of the undersigned and to act as attorney-in-fact, with full power of
substitution, for the undersigned in connection with the consummation of the
transactions contemplated by the Stock Exchange Agreement. All Avtel options
received are to be registered in the same name as the Matrix options held by the
undersigned.

(g)  The undersigned hereby represents and warrants that the undersigned has
full power to direct the exchange of the Matrix options as set forth above and
that the options to acquire shares of Matrix common stock to be exchanged by the
undersigned are free and clear of any liens or encumbrances.

                                      A-23

 
(h)  The undersigned understands that a false statement herein may be a
violation of law and could result in a claim for damages against the
undersigned.

(i)  The undersigned understands and agrees that the undersigned shall receive
the number of options to acquire Avtel shares listed below, that the exercise
price of such options shall be $2.24 per share, that all such options shall be
fully vested when issued and that the options shall expire at the close of
business on December 31, 2002 unless they shall have been exercised by the
undersigned on or before such date.


                              Signature________________________________

                              Print Name______________________________

                              Date:___________________________________

                              No. of Matrix Options Held:_________

                              No. of Avtel Options to be acquired:_________

                                      A-24