FIDELITY BANKSHARES, INC. CHANGEIN CONTROL AGREEMENT FOR ROBERT L. FUGATE

Exhibit 10.3(a)

FIDELITY BANKSHARES, INC.

CHANGE IN CONTROL AGREEMENT

FOR

ROBERT L. FUGATE

This AGREEMENT is made effective as of January 1, 2004 by and between Fidelity Bankshares, Inc., a Delaware corporation (the “Company”) with its principal office at 205 Datura Street, West Palm Beach, Florida 33401, and Robert L. Fugate (the “Executive”).

WHEREAS, the Executive has been elected to, and has agreed to serve in the position of Executive Vice President and Banking Operations Manager for the Fidelity Federal Bank and Trust (the “Bank”), the wholly-owned subsidiary of the Company a position of substantial responsibility;

WHEREAS, the Company recognizes the substantial contribution the Executive has made to the Bank and the Company and wishes to protect his position therewith for the period provided in this Agreement; and

NOW, THEREFORE, in consideration of the contribution of the Executive, and upon the other terms and conditions hereinafter provided, the parties hereto agree as follows:

1. TERM OF AGREEMENT

The term of this Agreement shall be deemed to have commenced as of the date first above written and shall continue for a period of thirty-six (36) full calendar months thereafter. Commencing on the first anniversary date of this Agreement (“Anniversary Date”) and continuing at each Anniversary Date thereafter, the Board of Directors of the Company (the “Board”) may extend the Agreement for an additional year. The Board will conduct a performance evaluation of the Executive for purposes of determining whether to extend the Agreement, and the results thereof shall be included in the minutes of the Board’s meeting.

2. PAYMENTS TO EXECUTIVE UPON CHANGE IN CONTROL

(a) Upon the occurrence of a Change in Control of the Bank or the Company (as herein defined) followed at any time during the term of this Agreement by the voluntary or involuntary termination of the Executive’s employment, other than for Cause, as defined in Section 2(c) hereof, the provisions of Section 3 shall apply. Upon the occurrence of a Change in Control, the Executive shall have the right to elect to voluntarily terminate his employment at any time during the term of this Agreement following any demotion, loss of title, office or significant authority, reduction in his annual compensation or benefits, or relocation of his principal place of employment by more than 30 miles from its location immediately prior to the Change in Control.

(b) A “Change in Control” of the Bank or the Company shall mean a change in control of a nature that: (i) would be required to be reported in response to Item 1(a) of the

current report on Form 8-K, as in effect on the date hereof, pursuant to Section 13 or 15(d) of the Securities Exchange Act of 1934 (the “Exchange Act”); or (ii) results in a Change in Control of the Bank or the Company within the meaning of the Home Owners’ Loan Act, as amended, and applicable rules and regulations promulgated thereunder (collectively, the “HOLA”) as in effect at the time of the Change in Control; or (iii) without limitation such a Change in Control shall be deemed to have occurred at such time as (a) any “person” (as the term is used in Sections 13(d) and 14(d) of the Exchange Act) is or becomes the “beneficial owner” (as defined in Rule 13d-3 under the Exchange Act), directly or indirectly, of securities of the Company representing 25% or more of the combined voting power of Company’s outstanding securities, except for any securities purchased by the Bank’s employee stock ownership plan or trust; or (b) individuals who constitute the Board on the date hereof (the “Incumbent Board”) cease for any reason to constitute at least a majority thereof, provided that any person becoming a director subsequent to the date hereof whose election was approved by a vote of at least three-quarters of the directors comprising the Incumbent Board, or whose nomination for election by the Company’s stockholders was approved by the same Nominating Committee serving under an Incumbent Board, shall be, for purposes of this clause (b), considered as though he were a member of the Incumbent Board; or (c) a plan of reorganization, merger, consolidation, sale of all or substantially all the assets of the Bank or the Company or similar transaction in which the Bank or Company is not the surviving institution occurs; or (d) a proxy statement soliciting proxies from stockholders of the Company, by someone other than the current Board of Directors of the Company, seeking stockholder approval of a plan of reorganization, merger or consolidation of the Company or similar transaction with one or more corporations as a result of which the outstanding shares of the class of securities then subject to the plan are exchanged for or converted into cash or property or securities not issued by the Company; or (e) a tender offer is made for 25% or more of the voting securities of the Company and the shareholders owning beneficially or of record 25% or more of the outstanding securities of the Company have tendered or offered to sell their shares pursuant to such tender offer and such tendered shares have been accepted by the tender offeror.

(c) The Executive shall not have the right to receive termination benefits pursuant to Section 3 hereof upon Termination for Cause. The term “Termination for Cause” shall mean termination because of the Executive’s intentional failure to perform stated duties, personal dishonesty, incompetence, willful misconduct, any breach of fiduciary duty involving personal profit, willful violation of any law, rule, regulation (other than traffic violations or similar offenses) or final cease and desist order, or any material breach of any material provision of this Agreement. In determining incompetence, the acts or omissions shall be measured against standards generally prevailing in the savings institution industry. For purposes of this paragraph, no act or failure to act on the part of the Executive shall be considered “willful” unless done, or omitted to be done, by the Executive not in good faith and without reasonable belief that the Executive’s action or omission was in the best interest of the Company. Notwithstanding the foregoing, the Executive shall not be deemed to have been terminated for Cause unless and until there shall have been delivered to him a copy of a resolution duly adopted by the affirmative vote of not less than three-fourths of the members of the Board at a meeting of the Board called and held for that purpose (after reasonable notice to the Executive and an opportunity for him, together with counsel, to be heard before the Board), finding that in the good faith opinion of the Board, the Executive was guilty of conduct justifying Termination for Cause and specifying the

2

particulars thereof in detail. The Executive shall not have the right to receive compensation or other benefits for any period after Termination for Cause. Any stock options granted to Executive under any stock option plan of the Company or any subsidiary or affiliate thereof, shall become null and void effective upon Executive’s receipt of Notice of Termination for Cause pursuant to Section 5 hereof, and shall not be exercisable by Executive at any time subsequent to such Termination for Cause.

3. TERMINATION

Upon the occurrence of a Change in Control, followed at any time during the term of this Agreement by the involuntary termination of the Executive’s employment (other than for Termination for Cause) or voluntary termination for one or more of the reasons set forth in Section 2(a) hereof, the Company shall be obligated to pay the Executive, or in the event of his subsequent death, his beneficiary or beneficiaries, or his estate, as the case may be, the following:

(a) his earned but unpaid salary as of the date of termination of employment and the benefits to which he would be entitled as of the date of termination as a former employee under the Bank’s and/or the Company’s employee benefit plans and programs and compensation plans and programs;

(b) as severance pay, a sum equal to three times the sum of (i) the highest rate of base salary, and (ii) highest rate of bonus awarded to the Executive during the prior three years by the Bank and/or the Company, subject to applicable withholding taxes. At the election of Executive, which election is to be made on an annual basis during the month of January, and which election is irrevocable for the year in which made and upon the occurrence of a Change in Control, any payments shall be made in a lump sum, or paid bi-weekly during the remaining term of this Agreement following Executive’s termination. In the event that no election is made, payment to Executive will be made in a lump sum within sixty (60) days of the termination of employment. Such payments shall not be reduced in the event Executive obtains other employment following termination of employment;

(c) continued life insurance coverage for Executive and health care coverage (including dental) for Executive and Executive’s dependents at the Company’s own expense for a period of thirty-six (36) months following termination of employment (at the end of which, Executive shall be entitled to elect the maximum continued health care coverage available in accordance with the COBRA provisions of Section 4980B of the Code) and such coverage shall be substantially identical to the coverage maintained by the Bank or the Company for the Executive prior to his severance;

(d) any outstanding unvested stock options or shares of restricted stock of the Company that have been awarded to him, which shall become fully vested as of his termination of employment;

(e) within sixty (60) days (or within such shorter period to the extent that information can be reasonably obtained) following his termination of employment, a lump sum payment in

3

an amount equal to the present value of the Bank’s contributions that would have been made on Executive’s behalf under the Bank’s 401(k) Plan and employee stock ownership plan (and any other defined contribution plan maintained by the Bank) if he had continued working for the Bank for a thirty-six (36) month period following his termination, earning the Base Salary that would have been achieved during the remaining unexpired term of this Agreement (assuming, if a Change in Control has occurred, that the annual Base Salary increases at the rate of six percent (6%) per year on each Anniversary Date over the remaining unexpired term of the Agreement) and making the maximum amount of employee contributions permitted, if any, under such plan or plans, where such present values are to be determined using a discount rate of six percent (6%) per year;

(f) within sixty (60) days (or within such shorter period to the extent that information can reasonably be obtained) following his termination of employment with the Bank, a lump sum payment in an amount equal to the excess, if any, of (A) the present value of the benefits to which he would be entitled under the Supplemental Executive Retirement Plan (and any other deferred compensation plan for management or highly compensated employees that are maintained by the Bank) if he had continued working for the Bank for the thirty-six (36) month period following his termination at the Base Salary and bonus that would have been achieved during the remaining unexpired term of this Agreement (assuming, if a Change in Control has occurred, that annual Base Salary and bonus each increase at the rate of six percent (6%) per year on each Anniversary Date for the remaining unexpired term of the Agreement) over (B) the present value of the benefits to which he is actually entitled under any such plan, as of the date of his termination with the Bank, where the present values are to be determined using a discount rate of six percent (6%) and the mortality tables prescribed under Section 72 of the Code.

4. ADDITIONAL PAYMENTS RELATED TO A CHANGE IN CONTROL

(a) In each calendar year that Executive is entitled to receive payments or benefits under the provisions of the Bank Change in Control Agreement, this Agreement and/or a Company or Bank sponsored employee benefit plan, the independent accountants of the Company shall determine if an excess parachute payment (as defined in Section 4999 of the Code) exists. Such determination shall be made after taking any reductions permitted pursuant to Section 280G of the Code and the regulations thereunder. Any amount determined to be an excess parachute payment after taking into account such reductions shall be hereafter referred to as the “Initial Excess Parachute Payment.” As soon as practicable after a Change in Control, the Initial Excess Parachute Payment shall be determined. For purposes of this determination, Executive shall be deemed to pay federal income taxes at the highest marginal rate of federal income tax (including, but not limited to, the Alternative Minimum Tax under Code Sections 55-59, if applicable) and state and local income tax, if applicable, at the highest marginal rate of taxation in the state and locality of Executive’s residence on the date such payment is payable, net of the maximum reduction in the federal income taxes which could be obtained from any available deduction of such state and local taxes. Any determination by the independent accountants shall be binding on the Company and Executive. Within five (5) days after such determination, the Company shall pay Executive, subject to applicable withholding requirements under applicable state or federal law an amount equal to:

(i) twenty (20) percent of the Initial Excess Parachute Payment (or such other amount equal to the tax imposed under Section 4999 of the Code), and

4

(ii) such additional amount (tax allowance) as may be necessary to compensate Executive for the payment by Executive of state and federal income and excise taxes on the payment provided under Clause (i) and on any payments under this Clause (ii). In computing such tax allowance, the payment to be made under Clause (i) shall be multiplied by the “gross up percentage” (“GUP”). The GUP shall be determined as follows:

The Tax Rate for purposes of computing the GUP shall be the highest marginal federal and state income and employment-related tax rate, including any applicable excise tax rate, applicable to Executive in the year in which the payment under Clause (i) is made.

(c) Notwithstanding the foregoing, if it shall subsequently be determined in a final judicial determination or a final administrative settlement to which Executive is a party that the excess parachute payment as defined in Section 4999 of the Code, reduced as described above, is different from the Initial Excess Parachute Payment (such different amount being hereafter referred to as the “Determinative Excess Parachute Payment”) then the Company’s independent accountants shall determine the amount (the “Adjustment Amount”) Executive must pay to the Company or the Company must pay to Executive in order to put Executive (or the Company, as the case may be) in the same position as Executive (or the Company, as the case may be) would have been if the Initial Excess Parachute Payment had been equal to the Determinative Excess Parachute Payment. In determining the Adjustment Amount, the independent accountants shall take into account any and all taxes (including any penalties and interest) paid by or for Executive or refunded to Executive or for Executive’s benefit. As soon as practicable after the Adjustment Amount has been so determined, the Company shall pay the Adjustment Amount to Executive or Executive shall repay the Adjustment Amount to the Company, as the case may be. The purpose of this paragraph is to assure that (i) Executive is not reimbursed more for the golden parachute excise tax than is necessary to make him whole, and (ii) if it is subsequently determined that additional golden parachute excise tax is owed by him, additional reimbursement payments will be made to him to make him whole for the additional excise tax.

(d) In each calendar year that Executive receives payments or benefits under the Bank Change in Control Agreement and/or this Agreement and/or a Company or Bank sponsored employee benefit plan, Executive shall report on his state and federal income tax returns such information as is consistent with the determination made by the independent accountants of the Company as described above. The Company shall indemnify and hold Executive harmless from any and all losses, costs and expenses (including without limitation, reasonable attorney’s fees, interest, fines and penalties) that Executive incurs as a result of so reporting such information. Executive shall promptly notify the Company in writing whenever Executive receives notice of the institution of a judicial or administrative proceeding, formal or informal, in which the federal tax treatment under Section 4999 of the Code of any amount paid or payable under this Section

5

is being reviewed or is in dispute. The Company shall assume control at its expense over all legal and accounting matters pertaining to such federal tax treatment (except to the extent necessary or appropriate for Executive to resolve any such proceeding with respect to any matter unrelated to amounts paid or payable pursuant to this contract). Executive shall cooperate fully with the Company in any such proceeding. Executive shall not enter into any compromise or settlement or otherwise prejudice any rights the Company may have in connection therewith without prior consent of the Company.

5. NOTICE OF TERMINATION

(a) Any purported termination by the Bank or by the Executive shall be communicated by Notice of Termination to the other party hereto. For purposes of this Agreement, a “Notice of Termination” shall mean a written notice which shall indicate the specific termination provision in this Agreement relied upon and shall set forth in reasonable detail the facts and circumstances claimed to provide a basis for termination of the Executive’s employment under the provision so indicated.

(b) “Date of Termination” shall mean (A) if the Executive’s employment is terminated for Disability, thirty (30) days after a Notice of Termination is given (provided that he shall not have returned to the performance of his duties on a full-time basis during such thirty (30) day period), and (B) if his employment is terminated for any other reason, the date specified in the Notice of Termination (which, in the case of a Termination for Cause, shall be immediate). Except as set forth below in paragraph (c), in no event shall the Date of Termination exceed 30 days from the date Notice of Termination is given.

(c) If, within thirty (30) days after any Notice of Termination is given, the party receiving such Notice of Termination notifies the other party that a dispute exists concerning the termination, except upon the occurrence of a Change in Control and voluntary termination by the Executive, in which case the date of termination shall be the date specified in the Notice, the Date of Termination shall be the date on which the dispute is finally determined, either by mutual written agreement of the parties, by a binding arbitration award, or by a final judgment, order or decree of a court of competent jurisdiction (the time for appeal therefrom having expired and no appeal having been perfected) and provided further that the Date of Termination shall be extended by a notice of dispute only if such notice is given in good faith and the party giving such notice pursues the resolution of such dispute with reasonable diligence. Notwithstanding the pendency of any such dispute, the Bank will continue to pay the Executive his full compensation in effect when the notice giving rise to the dispute was given (including, but not limited to, Base Salary) and continue him as a participant in all compensation, benefit and insurance plans in which he was participating when the notice of dispute was given, until the earlier of 120 days from the date of the Notice of Termination or the date upon which the dispute is finally resolved in accordance with this Agreement. Amounts paid under this Section are in addition to all other amounts due under this Agreement and shall not be offset against or reduce any other amounts due under this Agreement. Notwithstanding the foregoing, no compensation or benefits shall be paid to the Executive in the event the Executive is Terminated for Cause. In the event that such Termination for Cause is found to have been wrongful or such dispute is otherwise decided in the Executive’s favor, the Executive shall be entitled to receive all compensation and benefits which accrued for up to a period of nine months after the Termination for Cause.

6

6. SOURCE OF PAYMENTS

(a) All payments provided in this Agreement shall be timely paid in cash or check from the general funds of the Company. Executive and the Company, however, acknowledge that pursuant to that certain Change in Control Agreement between Executive and the Company dated as of the date of this Agreement (the “Company Change in Control Agreement”), the Company has guaranteed payment and provision of all amounts and benefits due hereunder to Executive and, if such amounts and benefits due from the Bank are not timely paid or provided by the Bank, such amounts and benefits shall be paid or provided by the Company.

(b) Notwithstanding any provision herein to the contrary, to the extent that payments and benefits, as provided in this Agreement, are paid to or received by Executive under the Company Change in Control Agreement, such compensation payments and benefits will be subtracted from any amounts due simultaneously to Executive under similar provisions of this Agreement.

(c) For financial statement purposes, termination payments made pursuant to the provisions of Section 3 of each of the Agreements shall be charged and paid in accordance with the terms of Section 3(g) of the Bank Change in Control Agreement and Section 4 of this Agreement.

7. EFFECT ON PRIOR AGREEMENTS AND EXISTING BENEFIT PLANS

This Agreement contains the entire understanding between the parties hereto and supersedes any prior agreement between the Bank and the Executive, except that this Agreement shall not affect or operate to reduce any benefit or compensation inuring to the Executive of a kind elsewhere provided. No provision of this Agreement shall be interpreted to mean that the Executive is subject to receiving fewer benefits than those available to him without reference to this Agreement.

8. NO ATTACHMENT

(a) Except as required by law, no right to receive payments under this Agreement shall be subject to anticipation, commutation, alienation, sale, assignment, encumbrance, charge, pledge, or hypothecation, or to execution, attachment, levy, or similar process or assignment by operation of law, and any attempt, voluntary or involuntary, to affect any such action shall be null, void, and of no effect.

(b) This Agreement shall be binding upon, and inure to the benefit of, the Executive, the Bank and their respective successors and assigns.

7

9. MODIFICATION AND WAIVER

(a) This Agreement may not be modified or amended except by an instrument in writing signed by the parties hereto.

(b) No term or condition of this Agreement shall be deemed to have been waived, nor shall there be any estoppel against the enforcement of any provision of this Agreement, except by written instrument of the party charged with such waiver or estoppel. No such written waiver shall be deemed a continuing waiver unless specifically stated therein, and each such waiver shall operate only as to the specific term or condition waived and shall not constitute a waiver of such term or condition for the future or as to any act other than that specifically waived.

10. REGULATORY PROVISIONS

Notwithstanding anything herein contained to the contrary, any payments to the Executive by the Company are subject to and conditioned upon their compliance with Section 18(k) of the Federal Deposit Insurance Act, 12 U.S.C. Section 1828(k), and the regulations promulgated thereunder in 12 C.F.R. Part 359.

11. SEVERABILITY

If, for any reason, any provision of this Agreement, or any part of any provision, is held invalid, such invalidity shall not affect any other provision of this Agreement or any part of such provision not held so invalid, and each such other provision and part thereof shall to the full extent consistent with law continue in full force and effect.

12. HEADINGS FOR REFERENCE ONLY

The headings of sections and paragraphs herein are included solely for convenience of reference and shall not control the meaning or interpretation of any of the provisions of this Agreement.

13. GOVERNING LAW

The validity, interpretation, performance, and enforcement of this Agreement shall be governed by the laws of the State of Florida, unless preempted by Federal law as now or hereafter in effect.

Except as otherwise expressly provided elsewhere in this Agreement, in the event that any dispute should arise between the parties as to the meaning, effect, performance, enforcement, or other issue in connection with this Agreement, which dispute cannot be resolved by the parties, the dispute shall be decided by final and binding arbitration of a panel of three arbitrators. Proceedings in arbitration and its conduct shall be governed by the rules of the American Arbitration Association (“AAA”) applicable to commercial arbitrations (the “Rules”) except as modified by this Section. The Employee shall appoint one arbitrator, the Company

8

shall appoint one arbitrator, and the third shall be appointed by the two arbitrators appointed by the parties. The third arbitrator shall be impartial and shall serve as chairman of the panel. The parties shall appoint their arbitrators within thirty (30) days after the demand for arbitration is served, failing which the AAA promptly shall appoint a defaulting party’s arbitrator, and the two arbitrators shall select the third arbitrator within fifteen (15) days after their appointment, or if they cannot agree or fail to so appoint, then the AAA promptly shall appoint the third arbitrator. The arbitrators shall render their decision in writing within thirty (30) days after the close of evidence or other termination of the proceedings by the panel, and the decision of a majority of the arbitrators shall be final and binding upon the parties, nonappealable, except in accordance with the Rules and enforceable in accordance with the Florida Arbitration Code or any applicable successor legislation. Any hearings in the arbitration shall be held in the Palm Beach County, Florida unless the parties shall agree upon a different venue, and shall be private and not open to the public. Each party shall bear the fees and expenses of its arbitrator, counsel, and witnesses, and the fees and expenses of the third arbitrator shall be shared equally by the parties. The costs of the arbitration, including the fees of AAA, shall be borne as directed in the decision of the panel.

14. PAYMENT OF LEGAL FEES

All reasonable legal fees paid or incurred by the Executive pursuant to any dispute or question of interpretation relating to this Agreement shall be paid or reimbursed by the Company if the Executive is successful on the merits pursuant to a legal judgment, arbitration or settlement.

15. INDEMNIFICATION

The Company shall provide the Executive (including his heirs, executors and administrators) with coverage under a standard directors’ and officers’ liability insurance policy at its expense, or in lieu thereof, shall indemnify the Executive (and his heirs, executors and administrators) to the fullest extent permitted under federal law and as provided in the Company’s Charter and Bylaws against all expenses and liabilities reasonably incurred by him in connection with or arising out of any action, suit or proceeding in which he may be involved by reason of his having been a director or officer of the Company (whether or not he continues to be a director or officer at the time of incurring such expenses or liabilities), such expenses and liabilities to include, but not be limited to, judgments, court costs and attorneys’ fees and the cost of reasonable settlements.

16. SUCCESSOR TO THE COMPANY

The Company shall require any successor or assignee, whether direct or indirect, by purchase, merger, consolidation or otherwise, to all or substantially all the business or assets of the Company, expressly and unconditionally 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 if no such succession or assignment had taken place.

9

16. SIGNATURES

IN WITNESS WHEREOF, the Company has caused this Agreement to be executed by its duly authorized officer, and the Executive has signed this Agreement, on the day and date first above written.

10