<PAGE>
 
                                 Exhibit 10.25

                                                        Frontier Corporation
LOGO 
frontier                        Joseph P. Clayton       180 South Clinton Avenue
                                President and CEO       Rochester, NY 14646
                                                        716-777-4900 
                                                        716-325-7639 fax



January 1, 1998

Mr. Martin T. McCue
14 Fall Meadow Drive
Pittsford, New York   14534

Dear Martin:

The Board of Directors (the "Board") of Frontier Corporation, on behalf of
Frontier and its subsidiaries and affiliates (together, the "Company") has
determined that it is in the best interests of the Company and its shareowners
to retain your services for the future and in case of a "Change of Control", as
defined later in this letter agreement ("Agreement").   It is therefore the
intent of this Agreement to assure your complete dedication to the Company by
providing you with compensation and benefits arrangements while you fulfill your
duties during the pendency of a Change of Control, should such an event occur,
which provide you with a measure of security commensurate with your importance
to the Company, and to assure itself of continuity in its relationship with
customers and employees.

Therefore, upon your signature on a counterpart of this Agreement, the following
terms and conditions shall become effective as stated below.  However, this
Agreement does not supersede any stock option agreements or restricted stock
grant agreements between the Company and you, all of which shall remain in full
force and effect.

1.   Employment.
     ---------- 

     1.1   Term.   The Company shall employ you in an executive position as
           ----                                                            
Senior Vice President and General Counsel at the Senior Vice President level, or
in such comparable management capacity as the Company may from time to time
designate.  This Agreement shall become effective as of January 1, 1998.   This
Agreement shall continue from year to year thereafter, unless earlier terminated
or extended in accordance with its terms. You acknowledge that, except as set
forth in this Agreement, your employment is "at will".

     If, during the Term, a "person" (as that term is used in Sections 13(d) and
14(d) of the Securities Exchange Act of 1934, as amended (the "Exchange Act"))
commences any action that, if consummated, would result in a Change of Control
of the Company  or if any person publicly announces an intention or proposal to
commence any such action, you agree that you will not leave the Company's employ
(other than as a result of death or Disability), you will render the services
contemplated in this Agreement for the reasonable duration of the Company's
defense against such action and until such action has been abandoned or
terminated or a Change in Control has occurred, and you will actively promote
the Company's interest during such period.
<PAGE>
 
     Any termination of your employment during the Term for reasons other than
your death shall be evidenced by a written notice ("Notice of Termination"),
which shall specify the provision of this Agreement relied upon for such
termination and describe with reasonable detail the facts and circumstances
claimed by the sender of such Notice of Termination to provide the basis for
termination.  Any such Notice of Termination shall also specify the effective
date of termination (the "Termination Date").  If you die during the Term, the
Termination Date shall be the date of your death, except as otherwise provided
herein.

     1.2   Present and Future Duties.   Your role in the Company shall be that
           -------------------------                                          
of its principal legal officer, with authority related to all internal and
external legal work done on behalf of the Company and its subsidiaries and
affiliates, and related responsibility for the regulatory work and government
relations of the Company, as such regulatory and government relations work is
currently allocated to you.  You shall perform all duties required of or
incidental to your position with the Company, or as may be assigned to you.  You
agree to use your best efforts in the business of the Company and to devote your
full time attention and energy to the business of the Company.  You agree not to
work, either on a part-time or independent contracting or consulting basis, with
or without compensation, for any other business or enterprise during the Term
without the Company's prior consent.  Such consent shall not be unreasonably
withheld in the case of service on the boards of directors of other corporations
and community organizations.

     1.3   Base Compensation.   The Company shall pay you as base compensation
           -----------------                                                  
at an annual salary rate of $240,000, in installments in accordance with the
Company's policies from time to time in effect. Thereafter, your annual salary
may be further adjusted by the Company consistent with the Company's results and
your performance during the prior year.  However, unless the annual salaries of
all senior executives of the Company are reduced across-the-board, your annual
salary in any year shall not be less than your annual salary during the prior
year.

     1.4   Incentive Compensation.   The Company shall establish and review with
           ----------------------                                               
you from time to time the performance goals ("Performance Goals") for the
Company and for you individually, and a methodology for calculating the amount
of incentive compensation to be paid upon achievement of such Performance Goals.
Your eligibility for a corporate bonus will be calculated on the same basis as
other similarly situated executives. Your incentive will be based on the success
of the Company as reflected in increased shareowner value, with such metrics to
be mutually agreed upon by you with the Chief Executive Officer of the Company,
and with the subsequent concurrence of the Board.  Incentive compensation shall
be payable to you at such time or times as are established under the Company's
policies (including the Company's Executive Compensation Program) in effect from
time to time.

     1.5   Benefits; Perquisites.   You shall be entitled to receive the
           ---------------------                                        
benefits and perquisites provided by the Company under its Executive
Compensation program in effect from time to time for executives at the Senior
Vice President level.

     1.6   Expenses.   You shall be reimbursed for any reasonable expenses
           --------                                                       
prudently incurred in connection with your employment during the Term, upon
presentation to the
<PAGE>
 
Company of an itemized account and receipts of such expenses as required by the
Company's policies from time to time in effect.

2.   Developments and Intellectual Property.   You acknowledge that all
     --------------------------------------                            
developments, including but not limited to trade secrets (including strategies,
business plans and customer lists), discoveries, improvements, ideas and
writings which either directly or indirectly relate to or may be useful in the
business of the Company (the "Developments") which you, either alone or in
conjunction with any other person or persons, shall conceive, make, develop,
acquire or acquire knowledge of during the Term are the sole and exclusive
property of the Company.  You will cooperate with the Company's reasonable
requests to obtain or maintain rights or protections under United States or
foreign law with respect to all Developments.  The Company will reimburse you
for all reasonable expenses incurred by you in order to comply with this
provision of this Agreement, regardless of when such expenses may be incurred.

3.   Confidential Information.   You acknowledge that by reason of your
     ------------------------                                          
employment by the Company, especially as a senior executive thereof, you may now
or will in the future have access to information of the Company that the Company
deems to be confidential and/or proprietary, including but not limited to,
information about the Company's target markets and customer segments,
strategies, plans, products and services, methods of operation, employees,
financial forecasts and results, sales, profits, expenses, customer lists and
the relationships between the Company or a subsidiary and its customers,
suppliers and others who have business dealings with it.  You covenant and agree
that during the Term and thereafter, without time or geographic limitation, you
will not disclose any such information to any person without the prior written
authorization of the Chief Executive Officer of the Company or the Board.

     If your employment ends for any reason other than your death, you agree to
return promptly to Company all such information and any other tangible product
or document which has been produced or received by, or otherwise submitted to
you during your employment, and no copies shall be retained by you or made
available to any other person or entity.  This provision includes but is not
limited to information printed or stored on paper, magnetic tape, floppy disks,
hard drives or other computer storage media.

4.   Non-Competition.
     --------------- 

     4.1   Covenant. You and the Company acknowledge that you have a special,
           --------                                                          
unique and extraordinary expertise in telecommunications and in law, and that in
your employment with the Company, you will have continuing access to information
about the Company's target markets, strategies, plans, product or service
offerings, methods of operation, financial and operating expectations and
results, customer base, sales, marketing and pricing strategies, most valued
employees, and customer and supplier relationships.  In consideration of the
benefits provided to you under this Agreement, which you acknowledge are
independent consideration, you covenant and agree that during the Restricted
Period (as defined below), you will not, directly or indirectly, without the
Company's prior consent, own, manage, operate, finance, join, control or
participate in the ownership or control of, or be associated as an officer,
director, executive, partner or principal, agent, representative, consultant or
otherwise with, or use or permit your name to be used in connection with, any
enterprise that directly or indirectly competes (as defined
<PAGE>
 
below) with any telecommunications business of the Company in a Restricted Area
(as defined below). You acknowledge that so long as you are able to use your
skills for enterprises that do not directly or indirectly compete with the
business of the Company, you will not be unreasonably limited in your ability to
work.

     4.2  Definitions.
          ----------- 

          4.2.1  "Competes" means the production, marketing, promotion,
     distribution or selling of any product, capability, functionality or
     service of any person or entity other than the Company which resembles or
     competes with a product or service produced, marketed, promoted,
     distributed or sold by the Company (or to your knowledge was under
     development by the Company) during the period of your employment by the
     Company (whether under this Agreement or otherwise).

          4.2.2  "Restricted Area" means:

                 (a) The Standard Metropolitan Statistical Area (or the
          equivalent) in which any sales office, place of employment, business
          address or POP maintained by the Company is located; or

                 (b) Any state of the United States, any province of Canada or
          any foreign country from which the Company or any of its subsidiaries
          or affiliates derives more than $25 million in revenue.

          4.2.3  "Restricted Period" means:
 
                 (a) The period of your employment by the Company (whether under
          this Agreement or otherwise), if your employment is terminated because
          of your death or Disability;

                 (b) The period of your employment by the Company (whether under
          this Agreement or otherwise) and 24 months thereafter, if your
          employment is terminated by the Company for Cause or without Cause
          (and not by the Company following Change of Control);

                 (c) The period of your employment by the Company (whether under
          this Agreement or otherwise) and, if this Agreement is still in effect
          at the Termination Date, the number of months remaining in the Term at
          the Termination Date or 12 months, whichever is longer (but in no
          event more than 24 months), if you terminate your employment
          voluntarily (and not for Good Reason); or

                 (d) The period of your employment by the Company under this
          Agreement, if your employment is terminated by you for Good Reason or
          by the Company on any basis following Change of Control.

          4.2.4  Exception.   This Section shall not be construed to prohibit
                 ---------                                                   
     the ownership by you of not more than 1% of any class of securities of any
     corporation which competes with the Company and which has a class of
     securities registered
<PAGE>
 
     pursuant to the Securities Exchange Act of 1934, as amended (the "Exchange
     Act").

     4.3   Savings Clause.   You and the Company specifically agree that this
           --------------                                                    
covenant not to compete and its specific limitations constitute a reasonable
covenant under the circumstances and is supported by the consideration stated
above, and further agree that if, in the opinion of any court of competent
jurisdiction, any of the provisions of this Section 4 are ever determined by a
court to exceed the time, geographic scope or other limitations permitted by
applicable law in any jurisdiction, then such excessive provisions shall be
deemed reduced, in such jurisdiction only, to the maximum time, geographic scope
or other limitation permitted in such jurisdiction, and you agree to the
enforcement of the remainder of the covenant as so amended.

5.   Non-Solicitation.   You also covenant and agree that during the Restricted
     ----------------                                                          
Period set out in Section 4.2.3, and without regard to the activity or
activities in which you are engaging, whether it is within or without the
telecommunications industry, you will not, directly or through employees,
agents, recruiters, independent contractors or others:  (a) offer, promise,
provide or guarantee employment, work for compensation, business opportunity or
other means of financial gain, or solicit, invite an inquiry on employment or
other compensatory relationship, respond to such inquiry with a promise or grant
of an employment or other compensatory relationship, or otherwise seek to
influence any person to leave the Company or to undertake activities that would
be adverse to the Company's interests, where such person is employed by the
Company or is in an independent contractor relationship in which a majority of
their time is spent on Company-related activities, or is a supplier of services
to the Company who would thereafter become unavailable to provide such services
to the Company, or who has been in such an employment or independent contractor
relationship within the 12 months prior to your contact(s); or (b) solicit from,
convert, attempt to convert, divert business from, or attempt to divert business
from any of the Company's customers, customer accounts or locations, whether
such activity is intended to benefit you or any other person or entity, and
whether or not such activity is successful.

6.   Equitable Relief.   You specifically acknowledge that the restrictions
     ----------------                                                      
contained in each of Sections 2, 3, 4 and 5 of this Agreement are, in view of
the nature of the business of the Company, and your position with it, reasonable
and necessary to protect the legitimate interests of the Company, and that any
violation of the provisions of those Sections will result in irreparable injury
to the Company for which there would be no adequate remedy at law.  You also
acknowledge that the Company shall be entitled to preliminary and permanent
injunctive relief, without the necessity of proving actual damages, and to an
equitable accounting of all earnings, profits and other benefits arising from
such violation.  These rights shall be cumulative and in addition to any other
rights or remedies to which the Company may be entitled.  You agree to submit to
the jurisdiction of any New York State court located in Monroe County or the
United States District Court for the Western District of New York or of the
state court or the federal court located in or presiding over the county in
which the Company has its corporate headquarters at the applicable time in any
action, suit or proceeding brought by the Company to enforce its rights under
Sections 2, 3,4 and/or 5 of this Agreement, and that any separate claim you have
shall not constitute a defense to the enforcement of the covenants and
agreements in those paragraphs.
<PAGE>
 
7.   Company's Obligations upon Termination.   The sole obligations of the
     --------------------------------------                               
Company upon the termination of your employment are as set forth in this Section
7.  Any and all amounts to be paid to you in connection with your termination
shall be paid in a lump sum promptly after the Termination Date, but not more
than 30 days thereafter.   Under any provision of this Section 7 (other than
your election to voluntarily terminate your employment or a final decision
related to termination for Cause, as defined in Section 12.1) if your employment
shall end, you shall receive full and immediate credit for: (a) the number of
years of age required to reach age 50 (if any), and (b) completion of any
remaining service bridging (or any additional years of service as are remaining
for you to have completed), to retire as of the date your employment ends and to
gain immediately a full and unreduced pension from the Company under the
appropriate benefit plans in which you participate, plus full participation
immediately in such other benefit plans as you would have been entitled to
participate in had you remained an employee through normal retirement. In the
event you should die or become disabled within the terms of any benefit plan
during the Term, you shall be deemed to have retired one day prior to your death
or disability, and you, or your estate or spouse, as you may have designated,
shall receive the full benefits available to them in such capacity, from such
circumstance.   Any existing options and restricted stock you hold and that are
provided under a plan that provides for vesting into retirement will continue to
vest into your retirement to the extent provided in the applicable plan.

     7.1  Termination upon Disability or Death.   If your employment with the
          ------------------------------------                               
Company ends by reason of your death or Disability (as defined later in this
Agreement), the Company shall pay you all amounts earned or accrued through the
Termination Date but not paid as of the Termination Date, including:

          7.1.1  Base compensation;

          7.1.2  Reimbursement for reasonable and necessary expenses incurred by
     you on behalf of the Company during the Term;

          7.1.3  Pay for earned but unused vacation and floating holidays;

          7.1.4  All compensation you previously deferred (if any) to the extent
     not yet paid; and

          7.1.5  An amount equal to your "Pro Rata Bonus".  Your Pro Rata Bonus
     shall be determined by multiplying the "Bonus Amount" (as defined below) by
     a fraction, the numerator of which is the number of days in the fiscal year
     through the Termination Date and the denominator of which is 365.  The term
     "Bonus Amount" means for each period for which a bonus is payable to
     employees under the short term incentive compensation program then in
     effect and for which you have not yet been paid:  (i) a bonus at the level
     actually achieved by the Company for the fiscal year if you worked for the
     Company for the full fiscal year; and (ii)(a) a bonus established under the
     applicable plan using the level actually achieved for such prorated portion
     of the fiscal year in which the Termination Date occurs as relates to your
     actual employment, using such measurements as are used generally by the
     Company for monitoring employee bonus qualification; or (b) if you leave at
     a time
<PAGE>
 
     in which the performance of the Company is not measured generally by the
     Company for employee bonus purposes, then the bonus at standard level for
     the number of full months of the fiscal year that you worked for the
     Company.

     The amounts described in Sections 7.1.1 through 7.1.4, inclusive, are
called elsewhere in this Agreement, collectively, the "Accrued Compensation".

     Except as otherwise provided in this Section 7.1, your entitlement to any
other compensation or benefits shall be determined in accordance with the
Company's employee benefit plans and other applicable programs and practices,
including any long term compensation benefits, then in effect.

     7.2  Termination Without Cause.   If the Company terminates your
          -------------------------                                  
employment without Cause (as defined later in this Agreement and not in
anticipation of a Change of Control), the Company shall pay you:

          7.2.1  All Accrued Compensation;

          7.2.2  A Pro Rata Bonus (as defined in Section 7.1.5 above); and

          7.2.3  Severance ("Severance") equal to: (a) twice the sum of (i) the
     annual base compensation you would have received for the entire fiscal year
     in which the Termination Date occurs plus (ii) the Bonus Amount plus (iii)
     $15,000 (being the agreed cash equivalent of the annual value of the
     perquisites provided to you under the Company's Executive Compensation
     Program), plus (iv) the Company contributions which would have been made on
     your behalf to the 401(k) retirement savings plan maintained by the Company
     (b) reduced by the present value of such amounts identified in subpart (a)
     as are "parachute payments" within the meaning of Section 280G(b)(2) of the
     Internal Revenue Code of 1986, as amended (the "Code") in the event of a
     change of control of the Company, determined in accordance with Section
     280G(d)(4) of the Code.    The foregoing shall be in lieu of any other
     amount of severance relating to salary or bonus continuation to be received
     by you upon termination of your employment under any severance plan, policy
     or arrangement of the Company.

     In addition, the Company shall continue to provide to you and your family
at the Company's expense, for 24 months following the Termination Date, the life
insurance, medical, dental, vision and hospitalization benefits provided to you
and your family immediately prior to the Termination Date.

     Except as otherwise provided in this Section 7.2, your entitlement to any
other compensation or benefits shall be determined in accordance with the
Company's employee benefit plans and other applicable programs and practices
then in effect.

     7.3   Termination for Cause or Voluntary Termination.   If your employment
           ----------------------------------------------                      
is terminated for Cause (as defined later in this Agreement and not in
anticipation of a Change of Control), or if you voluntarily terminate your
employment other than for Good Reason, the Company shall pay you all Accrued
Compensation.  Except as otherwise provided in this Section 7.3, your
entitlement to any other compensation or benefits shall be
<PAGE>
 
determined in accordance with the Company's employee benefit plans and other
applicable programs and practices then in effect.

     7.4  Termination for Good Reason or by Company Following Change of Control.
          ---------------------------------------------------------------------
If you terminate your employment for Good Reason or the Company terminates your
employment in anticipation of or following a Change of Control, the Company
shall pay you:

          7.4.1  All Accrued Compensation;

          7.4.2  A Pro Rata Bonus; and

          7.4.3  Severance equal to:  (a) three times the sum of (i) the annual
     base compensation you would have received for the entire fiscal year in
     which the Termination Date occurs plus (ii) the Bonus Amount plus (iii)
     $15,000 (being the agreed cash equivalent of the annual value of the
     perquisites provided to you under the Company's Executive Compensation
     Program), plus (iv) the Company contributions which would have been made on
     your behalf to the 401(k) retirement savings plan maintained by the Company
     (b) reduced by the present value of such amounts identified in subsection
     (a) as are "parachute payments" within the meaning of Section 280G(b)(2) of
     the Code in the event of a change of control of the Company, determined in
     accordance with Section 280G(d)(4) of the Code.  The foregoing severance
     shall be in lieu of any other amount of severance relating to salary or
     bonus continuation to be received by you upon termination of your
     employment under any severance plan, policy or arrangement of the Company.

     In addition, the Company shall continue to provide to you and your family
at the Company's expense, for 36 months following the Termination Date, the life
insurance, medical, dental, vision and hospitalization benefits provided to you
and your family immediately prior to the Termination Date.

     The Company shall reimburse you for all reasonable legal fees and expenses
which you may incur following a Change of Control as a result of the Company's
attempts to contest the validity or enforceability of this Agreement or your
attempts to obtain or enforce any right or benefit provided to you under this
Agreement, provided any actions you have taken are determined to have been
undertaken in good faith and upon a reasonable basis.

     Except as otherwise provided in this Section 7.4, your entitlement to any
other compensation or benefits shall be determined in accordance with the
Company's employee benefit plans and other applicable programs and practices,
including any long term compensation benefits, then in effect.

8.   Gross-Up Payment.   Notwithstanding anything else in this Agreement, if it
     ----------------                                                          
is found that any or all of the payments made to you, including but not limited
to payments made by the Company, or under any plan or arrangement maintained by
the Company, to you or for your benefit (other than any additional payments
required under this Section 8) (the "Payments") or any income you receive in the
form of restricted stock of the Company or options of the Company, would be
subject to the excise tax imposed by Section 4999 of the Code or you incur any
interest or penalties with respect to such excise tax (such excise tax, together
with any such interest and penalties, collectively the "Excise Tax"), then you
are
<PAGE>
 
entitled to receive an additional payment (a "Gross-Up Payment") in an amount
such that, after you pay all taxes (including any interest or penalties imposed
with respect to such taxes), including, without limitation, any income taxes
(and any interest and penalties imposed with respect thereto) and Excise Tax
imposed upon the Gross-Up Payment, you will retain an amount of the Gross-Up
Payment equal to the Excise Tax imposed upon the Payments.  The procedures for
the calculation and contesting of any claim that such Excise Tax is due are set
forth in the Addendum.

9.   No Obligation to Mitigate Damages.   You are not required to mitigate
     ---------------------------------                                    
damages or the amount of any payment provided for under this Agreement by
seeking other employment or otherwise, and the amounts to be paid to you under
Section 7 of this Agreement shall not be reduced by any compensation you may
earn from other sources.  However, if, during any period that you would
otherwise be entitled to receive any payments or benefits under this Agreement,
you breach your obligations under Section 2, 3, 4 and/or 5 of this Agreement,
the Company may immediately terminate any and all payments and the provision of
benefits (to the extent permitted by law and the terms of the benefit plans
maintained by the Company from time to time) hereunder.

10.  Successor to Company.   The Company will require any successor or assignee
     --------------------                                                      
to all or substantially all of the business and/or assets of the Company,
whether by merger, sale of assets or otherwise, by agreement in form and
substance reasonably satisfactory to you, to assume and agree to perform the
Company's obligations under this Agreement in the same manner and to the same
extent that the Company would be required to perform them if such succession or
assignment had not taken place.  Such agreement of assumption must be express,
absolute and unconditional.  If the Company fails to obtain such an agreement
within three business days prior to the effective date of such succession or
assignment, you shall be entitled to terminate your employment under this
Agreement for Good Reason.

11.  Survival.   Notwithstanding the expiration or termination of this
     --------                                                         
Agreement,  except as otherwise specifically provided herein, your obligations
under Sections 2, 3, 4 and/or 5 of this Agreement and the obligations of the
Company under this Agreement shall survive and remain in full force and effect.

     This Agreement shall inure to the benefit of, and be enforceable by, your
personal and legal representatives, executors, administrators, successors,
heirs, distributees, devisees and legatees.  If you die while any amounts are
still payable to you, all such amounts, unless otherwise provided in this
Agreement, shall be paid in accordance with the terms of this Agreement to your
devisee(s), legatee(s) or other designee(s) or, if there is no such designee(s),
to your estate.

12.  Definitions.   Whenever used in this Agreement, the following terms shall
     -----------                                                              
have the meanings below:

     12.1   "Cause" means:

          12.1.1  You have willfully and continually failed to substantially
     perform your duties (other than due to an incapacity resulting from
     physical or mental illness or due to any actual or anticipated failure
     after you have given a Notice of Termination
<PAGE>
 
     for Good Reason) after a written demand for substantial performance is
     delivered to you by the Chief Executive Officer or the Board which
     specifically identifies the manner in which it is believed that you have
     not substantially performed your duties; or

          12.1.2  You have willfully engaged in conduct which is demonstrably
     and materially injurious to the Company (monetarily or otherwise),
     including but not limited to a breach of fiduciary duty; or

          12.1.3  You have willfully engaged in conduct which is illegal or in
     violation of a material provision of the Company's Code of Ethics; or

          12.1.4  You have been convicted of a felony or a crime involving moral
     turpitude; or

          12.1.5  You have violated the provisions of Section 2 and/or Section 3
     and/or Section 4 and/or Section 5 of this Agreement

and, in any of the events described in Sections 12.1.1 through 12.1.5 above, the
---                                                                             
Board    adopts a resolution or its minutes reflect a finding that in the good
faith opinion of the Board you were culpable for the conduct set forth in any of
Sections 12.1.1 through 12.1.5 and specifying the particulars thereof in detail.
For the purposes of this Agreement, no act or failure to act on your part shall
be considered willful unless done, or omitted to be done, by you not in good
faith and without reasonable belief that your action or omission was in the best
interests of the Company.  Any such resolution of the Board must receive the
affirmative vote of not less than three-quarters of the entire membership of the
Board at a meeting of the Board called and held for the purpose of considering
the issue, and you must receive reasonable notice of the meeting and have an
opportunity, with your counsel, to present your case to the Board.

     12.2 "Change of Control" means:

          12.2.1  The consummation of a consolidation or merger of the Company
     in which the Company is not the continuing or surviving corporation or
     pursuant to which the shares of the Company's common, voting equity are to
     be converted into cash, securities or other property.  For the purposes of
     this Agreement, a consolidation or merger with a corporation which was a
     wholly-owned direct or indirect subsidiary of the Company immediately
     before the consolidation or merger is not a Change of Control; or

          12.2.2  The sale, lease, exchange or other transfer (in one
     transaction or a series of related transactions) of all or substantially
     all of the Company's assets; or

          12.2.3  The approval by the Company's shareowners of any plan or
     proposal for the liquidation or dissolution of the Company; or

          12.2.4  Any person, as that term is used in Section 13(d) and 14(d) of
     the Exchange Act (other than the Company, any trustee or other fiduciary
     holding securities of the Company under an employee benefit plan of the
     Company, a direct
<PAGE>
 
     or indirect wholly-owned subsidiary of the Company or any other company
     owned, directly or indirectly, by the shareowners of the Company in
     substantially the same proportions as their ownership of the Company's
     common, voting equity), is or becomes the beneficial owner (within the
     meaning of Rule 13d-3 under the Exchange Act), directly or indirectly, of
     30% or more of the Company's then outstanding common, voting equity; or

          12.2.5  During any period of two consecutive years, individuals who at
     the beginning of such period constitute the Board, including for this
     purpose any new director (other than a director designated by a person who
     has entered into an agreement with the Company to effect a transaction
     described in this Section 12.2.5) whose election or nomination for election
     by the Company's shareowners was approved by a vote of at least two-thirds
     of the directors then still in office who were directors at the beginning
     of the period or whose election or nomination for election was previously
     so approved (the "Incumbent Board"), cease for any reason to constitute a
     majority of the Board.

     12.3 "Disability" means:

          12.3.1  Your absence from your duties with the Company on a full-time
     basis for 180 consecutive business days as a result of incapacity due to
     mental or physical illness; or

          12.3.2  A physical or mental condition which prevents you from
     satisfactorily performing your duties with the Company and such incapacity
     or condition is determined to be total and permanent by a physician
     selected by the Company or its insurers and reasonably acceptable to you
     and/or your legal representative.

     12.4 "Good Reason" means:

          12.4.1   Without your express written consent, after a Change of
     Control, a significant reduction in title and authority, or the assignment
     to you of duties with the Company or with a person, as that term is used in
     Section 13(d) and 14(d) of the Exchange Act, in control of the Company
     materially diminished from the duties assigned to you immediately prior to
     a Change of Control; or

          12.4.2   Without your express written consent, after a Change of
     Control, any reduction by the Company or any person, as that term is used
     in Section 13(d) and 14(d) of the Exchange Act, in control of the Company
     in your annual base compensation or annual bonus at Standard (or
     equivalent) rating from the amounts of such compensation and/or bonus in
     effect immediately before and during the fiscal year in which the Change of
     Control occurred (except that this Section 12.4.2 shall not apply to
     across-the-board salary or bonus reductions similarly affecting all
     executives of the Company and all executives of any person in control of
     the Company); or

          12.4.3   Without your express written consent, after a Change of
     Control, the failure by the Company or any person, as that term is used in
     Section 13(d) and 14(d) of the Exchange Act, in control of the Company to
     increase your annual base
<PAGE>
 
     compensation or annual bonus at Standard (or equivalent) rating at the
     times and in comparable amounts as they are increased for similarly
     situated senior executive officers of the Company and of any person, as
     that term is used in Section 13(d) and 14(d) of the Exchange Act, in
     control of the Company; or

          12.4.4   Without your express written consent, after a Change of
     Control, the failure by the Company or by any person, as that term is used
     in Section 13(d) and 14(d) of the Exchange Act, in control of the Company
     to continue in effect any benefit or incentive plan or arrangement (except
     any benefit plan or arrangement which expires by its own terms then in
     effect upon the occurrence of a Change of Control) in which you are
     participating at the time of the Change of Control, unless a replacement
     plan or arrangement with at least substantially similar terms is provided
     to you; or

          12.4.5   Without your express written consent, after a Change of
     Control, the taking of any action by the Company or by any person, as that
     term is used in Section 13(d) and 14(d) of the Exchange Act, in control of
     the Company which would adversely affect your participation in or
     materially reduce your benefits under any benefit plan or arrangement or
     deprive you of any other material benefit (including any miscellaneous
     benefit which is not represented and protected by a written plan document
     or trust) enjoyed by you at the time of a Change of Control; or

          12.4.6   You terminate your employment (other than because of your
     death or Disability) by giving the Company a Notice of Termination with a
     Termination Date not later than the first anniversary of the Change of
     Control; or

          12.4.7   Any failure by the Company to comply with any of its material
     obligations under this Agreement, after you have given notice of such
     failure to the Company and the Company has not cured such failure promptly
     after its receipt of such notice.

13.  Notice.   All notices and other communications required or permitted under
     ------                                                                    
this Agreement shall be in writing and shall be deemed given when mailed by
certified mail, return receipt requested, or by nationally recognized overnight
courier, receipt requested, when addressed to you at your official business
address when employed by the Company or at your home address as reflected in the
Company's records from time to time and when addressed to the Company at its
corporate headquarters, to the attention of the Board, with a required copy to
the Company's highest ranking legal executive or officer.

14.  Amendment and Assignment.   This Agreement cannot be changed, modified or
     ------------------------                                                 
terminated except in a writing.  You may not assign your duties with the Company
to any other person.  The Company may assign its obligations under this
Agreement to one of its principal subsidiaries for administrative purposes.

15.  Severability.   If any provision of this Agreement or the application of
     ------------                                                            
this Agreement to anyone or under any circumstances is determined by a court to
be invalid or unenforceable in any jurisdiction, such invalidity or
unenforceability shall not affect any other provisions or applications of this
Agreement which can be effective without the invalid
<PAGE>
 
or unenforceable provision or application, and such invalidity or
unenforceability shall not invalidate or render unenforceable such provision in
any other jurisdiction.

16.  Remedies Cumulative; No Waiver.   No remedy conferred on you or on the
     ------------------------------                                        
Company by this Agreement is intended to be exclusive of any other remedy, and
each and every remedy shall be cumulative and shall be in addition to any other
remedy given under this Agreement or now or later existing at law or in equity.
No delay or omission by you or by the Company in exercising any right, remedy or
power under this Agreement or existing at law or inequity shall be construed as
a waiver of such right, remedy or power, and any such right, remedy or power may
be exercised by you or the Company from time to time and as often as is
expedient or necessary.

17.  Governing Law.   This Agreement shall be governed by and construed in
     -------------                                                        
accordance with the laws of the State of New York, without regard to any
applicable conflicts of laws.

18.  Counterparts.   This Agreement may be signed by you and on behalf of the
     ------------                                                            
Company in one or more counterparts, each of which shall be one original but all
of which together will constitute one and the same instrument.

If this Agreement correctly sets forth our agreement on its subject matter,
please sign and return to me the enclosed copy of this Agreement.  Please keep
the other copy for your records.


Sincerely,

FRONTIER CORPORATION


By:  /s/ Joseph P. Clayton
     ---------------------
     Joseph P. Clayton
     Chief Executive Officer



Agreed to this 27th date of February, 1998, to be effective as of January 1,    
1998:


       /s/ Martin T. McCue
       -------------------
       Martin T. McCue
<PAGE>
 
           ADDENDUM TO LETTER AGREEMENT DATED AS OF JANUARY 1, 1998


     The following provisions shall apply to the calculation and procedures
relating to the Gross-Up Payment in accordance with Section 8 of the Agreement.

     1.  The Company's independent auditors in the fiscal year in which the
Change of Control occurs (the "Accounting Firm") shall determine whether and
when a Gross-Up Payment is required, the amount of such Gross-Up Payment and the
assumptions to be used in making such determination.  The Accounting Firm shall
provide detailed supporting calculations, together with a written opinion with
respect to the accuracy of such calculations, to you and the Company within 15
business days of the receipt of a written request from either you or the
Company.  If the Accounting Firm is serving (or has served within the three
years preceding the Change in Control) as accountant or auditor for the person
in control of the Company following the Change of Control or any affiliate
thereof, you may appoint another nationally recognized accounting firm to make
the determinations required in connection with the Gross-Up Payment and the
substitute accounting firm shall then be referred to as the Accounting Firm).
The Company shall pay you any Gross-Up Payment, determined in accordance with
this Addendum, within five days of the receipt of the Accounting Firm's
determination.  If the Accounting Firm determines that you will not be liable
for any Excise Tax, it shall furnish you with a written opinion that your
failure to report the Excise Tax on the applicable federal income tax return
would not result in the imposition of a negligence or similar penalty.  Any
determination by the Accounting Firm shall be binding upon you and the Company.

     2.  If there is uncertainty about how Section 4999 is to be applied when
the Accounting Firm makes its initial determination, and as a result the Gross-
Up Payment made to you by the Company is determined (after following the
procedures set forth in this Addendum) to be less than it should have been made
(an "Underpayment"), and you are thereafter required to pay any Excise Tax, the
Accounting Firm shall determine the amount of the Underpayment and any such
Underpayment shall be promptly paid by the Company to you or for your benefit.

     3.  You shall notify the Company in writing of any claim by the Internal
Revenue Service that, if successful, would require the Company to pay you the
Gross-Up Payment.  Your notice shall be given as soon as practicable but no
later than ten business days after you have been informed in writing of such
claim and shall apprise the Company of the nature of such claim and the date on
which such claim is requested to be paid.  You shall not pay such claim prior to
the expiration of the 30 day period following the date on which you gave such
notice to the Company (or any shorter period, if the taxes claimed are due
sooner).  If the Company notifies you in writing prior to the expiration of such
period that it desires to contest such claim, you shall:  (a) give the Company
any information reasonably requested by it relating to such claim, (b) take such
action in connection with contesting such claim as the Company shall reasonably
request in writing from time to time, including, without limitation, accepting
legal representation with respect to such claim by an attorney reasonably
selected by the Company, (c) cooperate with the Company in good faith in order
effectively to contest such claim, and (d) permit the Company to participate in
any proceedings relating to such claim.
<PAGE>
 
     4.  The Company shall control all proceedings taken in connection with such
contest and, at its sole option, may pursue or forgo any and all administrative
appeals, proceedings, hearings and conferences with the taxing authority in
connection with the claim and may, at its sole option, either direct you to pay
the tax claimed and sue for a refund or contest the claim in any permissible
manner, and you agree to prosecute the contest to a determination before any
administrative tribunal, in a court of initial jurisdiction and in one or more
appellate courts as the Company shall determine.

     5.  Any extension by the Company of the statute of limitations relating to
payment of taxes for the taxable year for which such contested amount is claimed
to be due shall be limited solely to such contested amount.  The Company's
control of the contest shall be limited to issues with respect to which a Gross-
Up Payment would be payable under this Agreement and you shall be entitled to
settle or contest, as the case may be, any other issue raised by the Internal
Revenue Service or any other taxing authority.

     6.  If the Company directs you to pay such claim and sue for a refund, the
Company shall advance the amount of such payment to you, on an interest-free
basis, and shall indemnify and hold you harmless, on an after-tax basis, from
any Excise Tax or income tax (including interest or penalties with respect
thereto) imposed with respect to such advance or with respect to any imputed
income with respect to such advance.

     7.  If you receive a refund of any amount advanced to you by the Company,
you will promptly pay to the Company the amount of such refund (together with
any interest paid or credited thereon after taxes applicable thereto). If the
Company advanced to you any amounts and a determination is made that you will
not be entitled to any refund with respect to such claim and the Company does
not notify you in writing of its intent to contest such denial of refund prior
to the expiration of 30 days after such determination, then such advance shall
be forgiven and you will not be required to be repay it.  The amount of such
advance shall offset the amount of the Gross-Up Payment required to be paid.

     8.  The Company shall pay all fees and expenses of the Accounting Firm.
The Company shall bear and pay directly all costs and expenses (including
additional interest and penalties) incurred in connection with such contest and
shall indemnify and hold you harmless, on an after-tax basis, for any Excise Tax
or income tax (including interest and penalties with respect thereto) imposed as
a result of such representation and payment of costs and expenses.