<PAGE>   1

                                                                     Exhibit 3.1

                                    RESTATED
                                (with amendments)

                          CERTIFICATE OF INCORPORATION

                                       of

                             MAGIC RESTAURANTS, INC.

            MAGIC RESTAURANTS, INC. (the "Corporation"), a corporation organized
and existing under and by virtue of the General Corporation Law of the State of
Delaware (the "Act"), DOES HEREBY CERTIFY:

            First. The current name of the Corporation is Magic Restaurants,
Inc. The date of filing of its original Certificate of Incorporation with the
Secretary of State was July 14, 1988, under the name Wetherly Ventures
Associates, Inc. The name of the Corporation was changed to Magic Restaurants,
Inc. in a filing with the Secretary of State dated October 28, 1988. After the
filing of the attached Restated (with amendments) Certificate of Incorporation,
the Corporation's name shall be changed to Redheads, Inc.

            Second. Pursuant to Section 303 of the General Corporation Law of
the State of Delaware, the Certificate of Incorporation is amended and restated
by an Order dated December 31, 1996 of the United States Bankruptcy Court for
the District of Delaware, In re Magic Restaurants, Inc., et al., Case No. 95-376
(Chapt. 11). The anticipated date of confirmation of said Order is December 31,
1996.


                                      Redhead, Inc. Certificate of Incorporation
<PAGE>   2

            Third: The Certificate of Incorporation of the Corporation is hereby
amended in its entirety and superseded by the Restated Certificate of
Incorporation attached hereto as Exhibit A.

            IN WITNESS WHEREOF, this Restated Certificate of Incorporation,
which has been duly adopted in accordance with the provisions of Section 303 of
the General Corporation Law of the State of Delaware, has been executed by
President of the Corporation and attested by its Secretary on this 12th day of
March, 1997.

                                                MAGIC RESTAURANTS, INC.


                                                By: /s/ Charles Olson, Jr.
                                                   -----------------------------
                                                   Charles Olson, Jr., President

ATTEST:


Sharon Lopez
------------------------
Sharon Lopez, Secretary


                                      -2-

                                      Redhead, Inc. Certificate of Incorporation
<PAGE>   3

                                    Exhibit A

                                    RESTATED

                          CERTIFICATE OF INCORPORATION

                                       of

                            REDHEADS BISTRO BAR, INC.

            FIRST: The name of the Corporation is Redheads Bistro Bar, Inc.

            SECOND: The address of its registered office in the State of
Delaware is 1209 Orange Street, in the City of Wilmington, County of New Castle
19801. The name of its registered agent at such address is The Corporation Trust
Company.

            THIRD: The nature of the business or purposes to be conducted or
promoted by the Corporation are: (i) to engage in any act or activity in
furtherance of and consistent with the Plan of Reorganization of the Corporation
confirmed by an Order dated December 31, 1996 of the United States Bankruptcy
Court for the District of Delaware, Case No. 95-376 (Chapt. 11), until such time
as said Court enters a final order or decree to the effect that the Corporation
is no longer required to operate under the Plan; and (ii) to engage in any
lawful act or activity for which corporations may be organized under the General
Corporation Laws of the State of Delaware.

            FOURTH: The total number of shares of all classes of capital stock
which the Corporation shall have authority to issue is 25,000,000, of which
5,000,000 shares shall be Preferred


                                      -1-
<PAGE>   4

Stock, par value $.01 per share, and 20,000,000 shares shall be Common Stock,
par value $.001 per share.

            A. Preferred Stock. (1) The Preferred Stock may be issued from time
      to time in one or more series and in such amounts as may be determined by
      the Board of Directors or by order or decree of a court of competent
      jurisdiction over this Corporation administering any applicable statute of
      the United States relating to plans of reorganization of corporations. The
      voting powers, designations, preferences and relative, participating,
      optional or other special rights, if any, and the qualifications,
      limitations or restrictions thereof, if any, of the Preferred Stock of
      each series shall be such as are fixed by the Board of Directors or fixed
      by such court, authority so to do being hereby expressly granted, and as
      are stated and expressed in a resolution or resolutions adopted by the
      Board of Directors or in an order or decree of such court providing for
      the issue of such series of Preferred Stock (herein called the "Preferred
      Stock Statement"). The Preferred Stock Statement as to any series shall
      (a) designate the series, (b) fix the dividend rate, if any, of such
      series, the payment dates for dividends on shares of such series and the
      date or dates, or the method of determining the date or dates, if any,
      from which dividends on shares of such series shall be cumulative, (c) fix
      the amount or amounts payable on shares of such series upon voluntary or
      involuntary liquidation, dissolution or winding up of the affairs of the
      corporation, (d) state the price or prices or rate or rates, and
      adjustments, if any, at which, the time or times and the terms and
      conditions upon which, the shares of such series may be redeemed at the
      option of the Corporation or at the option of the holder or holders of
      shares of such series or upon the


                                      -2-
<PAGE>   5

      occurrence of a specified event, and state whether such shares may be
      redeemed for cash, property or rights, including securities of the
      Corporation or another entity; and such Preferred Stock Statement may (i)
      limit the number of shares of such series that may be issued, (ii) provide
      for a sinking fund for the purchase or redemption of shares of such series
      and specify the terms and conditions governing the operations of any such
      fund, (iii) grant voting rights to the holders of shares of such series,
      provided that each share shall not have more than one vote per share, (iv)
      impose conditions or restrictions upon the creation of indebtedness of the
      Corporation or upon the issuance of additional Preferred Stock or other
      capital stock ranking on a parity therewith, or prior thereto, with
      respect to dividends or distribution of assets upon liquidation, (v)
      impose conditions or restrictions upon the payment of dividends upon, or
      the making of other distributions to, or the acquisition of, shares
      ranking junior to the Preferred Stock or to any series thereof with
      respect to dividends or distributions of assets upon liquidation, (vi)
      state the time or times, the price or prices or the rate or rates of
      exchange and other terms, conditions and adjustments upon which shares of
      any such series may be made convertible into, or exchangeable for, at the
      option of the holder or the Corporation or upon the occurrence of a
      specified event, shares of any other class or classes or of any other
      series of Preferred Stock or any other class or classes of stock or other
      securities of the Corporation, and (vii) grant such other special rights
      and impose such qualifications, limitations or restrictions thereof as
      rights and impose such qualifications, limitations or restrictions thereon
      as shall be fixed by the Board of Directors or such court, to the extent
      not inconsistent with this Article FOURTH and to the full extent now or
      hereafter permitted by the laws of the State of Delaware.


                                      -3-
<PAGE>   6

                  (2) Except as by law expressly provided, or except as may be
      provided in any Preferred Stock Statement, the Preferred Stock shall have
      no right or power to vote on any question or in any proceeding or to be
      represented at, or to receive notice of, any meeting of stockholders of
      the Corporation.

                  (3) Preferred Stock that is redeemed, purchased or retired by
      the Corporation shall assume the status of authorized and unissued
      Preferred Stock and may thereafter, subject to the provisions of any
      Preferred Stock Statement providing for the issue of any particular series
      of Preferred Stock, be reissued in same manner as authorized and unissued
      Preferred Stock.

            B. Common Stock. All shares of the Common Stock of the Corporation
      shall be identical and, except as otherwise required by law or as
      otherwise provided in the Preferred Stock Statement with respect to any
      series of Preferred Stock, the holders of the Common Stock shall
      exclusively possess all voting power, and each share of Common Stock shall
      have one vote.

            FIFTH: The number of directors constituting the Board of Directors
shall be fixed as specified in the Bylaws of the Corporation, but shall not be
less than three or more than 15. The directors shall be divided into three
classes, designated Class I, Class II and Class III. The initial term for
directors in Class I shall expire at the annual meeting of stockholders to be
held in 1997; the initial term for directors in Class II shall expire at the
annual meeting of stockholders to be held


                                      -4-
<PAGE>   7

in 1998; and the initial term for directors in Class III shall expire at the
annual meeting of stockholders to be held in 1999. Each class of directors shall
consist, as nearly as may be possible, of one-third of the total number of
directors constituting the entire Board of Directors.

            At the expiration of the initial term of each class of directors,
and of each succeeding term of each class, each class of directors shall be
elected to serve until the annual meeting of stockholders held three years from
such expiration and until their successors are elected and qualified or until
their earlier death, resignation, removal or retirement. Any increase or
decrease in the number of directors constituting the Board shall be apportioned
among the classes so as to maintain the number of directors in each class as
near as possible to one-third the whole number of directors as so adjusted. Any
director elected or appointed to fill a vacancy shall hold office for the
remaining term of the class to which such directorship is assigned. No decrease
in the number of directors constituting the Corporation's Board of Directors
shall shorten the term of any incumbent director. Any vacancy in the Board of
Directors, whether arising through death, resignation or removal of a director,
or through an increase in the number of directors of any class, shall be filled
by the majority vote of the remaining directors. The Bylaws may contain any
provision regarding classification of the Corporation's directors not
inconsistent with the terms hereof.

            A director of the Corporation may be removed only for cause and only
upon the affirmative vote of the holders of a majority of the outstanding
capital stock of the Corporation entitled to vote at an election of directors,
subject to further restrictions on removal, not inconsistent with this Article
FIFTH, as may be contained in the Bylaws.


                                      -5-
<PAGE>   8

            Notwithstanding the foregoing, whenever the holders of any one or
more classes or series of Preferred Stock issued by the Corporation shall have
the right, voting separately by class or series, to elect directors at an annual
or special meeting of stockholders, the election, term of office, filling of
vacancies and other features of such directorships shall be governed by the
terms of this Restated Certificate of Incorporation applicable thereto, and such
directors so elected shall not be divided into classes pursuant to this Article
FIFTH unless expressly provided by such terms.

            SIXTH: The following provisions are inserted for the management of
the business and the conduct of the affairs of the Corporation, and for further
definition, limitation and regulation of the powers of the Corporation and of
its directors and stockholders:

            A. The Board of Directors is authorized to alter, amend or repeal
      the Bylaws or adopt new Bylaws of the Corporation. The stockholders shall
      not repeal or change the Bylaws of the Corporation unless such repeal or
      change is approved by the affirmative vote of the holders of not less than
      80% of the total voting power of all shares of stock of the Corporation
      entitled to vote in the election of directors, considered for the purposes
      of this paragraph A as a single class.

            B. Election of directors need not be by written ballot unless the
      Bylaws so provide.


                                      -6-
<PAGE>   9

            C. In addition to the powers herein or by statute expressly
      conferred upon the Corporation's directors, the Corporation's directors
      are hereby empowered to exercise all such powers and do all such acts and
      things as may be exercised or done by the Corporation, subject,
      nevertheless, to the provisions of the statutes of Delaware, any plan of
      reorganization administered under an applicable statute of the United
      States relating to reorganizations of corporations and ordered or decreed
      by a court of competent jurisdiction, this Restated Certificate of
      Incorporation, and any Bylaws adopted by the stockholders; provided,
      however, that no Bylaws hereafter adopted shall invalidate any prior act
      of the directors which would have been valid if such Bylaws had not been
      adopted.

            D. No action shall be taken by the stockholders except at any annual
      or special meeting with prior notice and a vote. No action shall be taken
      by the stockholders by written consent.

            SEVENTH: The books of the Corporation may be kept (subject to any
provision contained in the statutes) outside the State of Delaware at such place
or places as may be designated from time to time by the Board of Directors or in
the Bylaws of the Corporation.

            EIGHTH: The Board of Directors is hereby authorized to create and
issue, whether or not in connection with the issuance and sale of any of its
stock or other securities, rights (the "Rights") entitling the holders thereof
to purchase from the Corporation shares of capital stock or other securities.
The times at which and the terms upon which the Rights are to be issued will be


                                      -7-
<PAGE>   10

determined by the Board of Directors and set forth in the contracts or
instruments that evidence the Rights. The authority of the Board of Directors
with respect to the Rights shall include, but not be limited to, determination
of the following:

            (a) The initial purchase price per share of the capital stock or
            other securities of the Corporation to be purchased upon exercise of
            the Rights.

            (b) Provisions relating to the times at which and the circumstances
            under which he Rights may be exercised or sold or otherwise
            transferred, either together with or separately from, any other
            securities of the Corporation.

            (c) Provisions that adjust the number of exercise price of the
            Rights or amount or nature of the securities or other property
            receivable upon exercise of the Rights in the event of a
            combination, split or recapitalization of any capital stock of the
            Corporation, a change in ownership of the Corporation's securities
            or a reorganization, merger, consolidation, sale of assets or other
            occurrence relating to the Corporation or any capital stock of the
            Corporation, and provisions restricting the ability of the
            Corporation to enter into any such transaction absent an assumption
            by the other party or parties thereto of the obligations of the
            Corporation under such Rights.


                                      -8-
<PAGE>   11

            (d) Provisions that deny the holder of a specified percentage of the
            outstanding securities of the Corporation the right to exercise the
            Rights and/or cause the Rights held by such holder to become void.

            (e) Provisions that permit the Corporation to redeem the Rights.

            (f) The appointment of a Rights Agent with respect to the Rights.

            NINTH: No director of the Corporation shall be personally liable to
the Corporation or its stockholders for monetary damages for breach of fiduciary
duty by such director as a director; provided, however, that this Article NINTH
shall not eliminate or limit the liability of a director to the extent provided
by applicable law (i) for any breach of the director's duty of loyalty to the
Corporation or its stockholders, (ii) for acts or omissions not in good faith or
which involve intentional misconduct or a knowing violation of law, (iii) under
Section 174 of the General Corporation Law of the State of Delaware or (iv) for
any transaction from which the director derived an improper personal benefit. No
amendment to or repeal of this Article NINTH shall apply to, or have any effect
on, the liability or alleged liability of any director of the Corporation for or
with respect to any facts or omissions of such director occurring prior to such
amendment or repeal. If the General Corporation Law of the State of Delaware is
amended to authorize corporate action further eliminating or limiting the
personal liability of directors, then the liability of a director of the
Corporation shall be eliminated or limited to the fullest extent permitted by
the General Corporation Law of the State of Delaware, as so amended.


                                      -9-
<PAGE>   12

            TENTH: The provisions set forth in Article FIFTH hereof may not be
amended, altered, changed, repealed or rescinded in any respect unless such
action is approved by the affirmative vote of the holders of not less than 80
percent of the total voting power of all shares of stock of the Corporation
entitled to vote in the election of directors, considered for purposes of this
Article TENTH as a single class; the amendment, alteration, change, repeal or
rescission of this Article TENTH and Articles SIXTH, EIGHTH and NINTH hereof
shall require the affirmative vote of holders of not less than 80 percent of the
total voting power of all shares of stock of the Corporation entitled to vote on
amendments to this Certificate of Incorporation. The voting requirements
contained in this Article TENTH and in Article SIXTH hereof shall be in addition
to voting requirements imposed by law, other provisions of this Restated
Certificate of Incorporation or any designation of preferences in favor of
certain classes or series of shares of capital stock of the Corporation.

            ELEVENTH: Whenever a compromise or arrangement is proposed between
this Corporation and its creditors or any class of them and/or between this
Corporation and its stockholders or any class of them, any court of equitable
jurisdiction within the State of Delaware may, on the application in a summary
way of this Corporation or of any creditor or stockholder thereof or on the
application of any receiver or receivers appointed for this Corporation under
ss.291 of Title 8 of the Delaware Code or on the application of trustees in
dissolution or of any receiver or receivers appointed for this Corporation, as
the case may be, to be summoned in such manner as the said court directs. If a
majority in number representing three-fourths in value of the creditors or class
of creditors, and/or of the stockholders or class of stockholders of this
Corporation, as the case may


                                      -10-
<PAGE>   13

be, agree to any compromise or arrangement and to any reorganization of this
Corporation as a consequence of such compromise or arrangement, the said
compromise or arrangement and the said reorganization shall, if sanctioned by
the court to which the said application has been made, be binding on all the
creditors or class of creditors, and/or on all the stockholders or class of
stockholders, of this Corporation, as the case may be, and also on this
Corporation.


                                      -11-