<PAGE>   1
                                                                   EXHIBIT 10.31











                                 FIRST AMENDMENT

                                       TO

                        NATURAL GAS ADVANCE SALE CONTRACT

                                     between

                        COLUMBIA NATURAL RESOURCES, INC.,
                                   as Seller,

                                       and

                               MAHONIA II LIMITED,
                                  as Purchaser,

                         Effective as of March 30, 2001
<PAGE>   2
              FIRST AMENDMENT TO NATURAL GAS ADVANCE SALE CONTRACT

           This FIRST AMENDMENT TO NATURAL GAS ADVANCE SALE CONTRACT (this
"First Amendment") executed effective as of the 30th of March, 2001 (the
"Effective Date") is between COLUMBIA NATURAL RESOURCES, INC., a Texas
corporation ("Seller"), and MAHONIA II LIMITED, a Jersey company ("Purchaser").

                                    RECITALS

           A. Seller and Purchaser are parties to that certain Natural Gas
Advance Sale Contract dated as of December 1, 1999 (the "Natural Gas Advance
Sale Contract") and that certain Confirmation of Natural Gas Advance Sale
executed on December 2, 1999 related thereto (the "Confirmation Letter"),
pursuant to which Seller sold, and Purchaser bought, certain volumes of Natural
Gas to be delivered by Seller to Purchaser in each calendar month commencing
with the month of February, 2000, through and including the month of October,
2004 (the "Existing Delivery Schedule").

           B. Seller has requested, and Purchaser has agreed, to amend certain
provisions of the Natural Gas Advance Sale Contract and the Confirmation Letter
to defer the Existing Delivery Schedule as set forth in Annex 1 attached hereto.

           C. In consideration of Purchaser's agreement to defer certain of
Seller's delivery obligations under the Natural Gas Advance Sale Contract and
the Confirmation Letter, Seller has agreed to increase the total volumes of
Natural Gas to be delivered by Seller to Purchaser under the Natural Gas Advance
Sale Contract and the Confirmation Letter in accordance with the terms hereof.

           D. NOW, THEREFORE, in consideration of the premises and the mutual
covenants herein contained, for good and valuable consideration, the receipt and
sufficiency of which are hereby acknowledged, the parties hereto agree as
follows:

           Section 1.Defined Terms. Each capitalized term which is defined in
the Natural Gas Advance Sale Contract, but which is not defined in this First
Amendment, shall have the same meaning as defined in the Natural Gas Advance
Sale Contract. Unless otherwise indicated, all section and paragraph references
in this First Amendment refer to sections and paragraphs of the Natural Gas
Advance Sale Contract.

           Section 2.Amendments to Natural Gas Advance Sale Contract.

           2.1       Amendments to Section 1.01.

           (a) The following definitions of "Amended and Restated Confirmation
Letter," "First Amendment" and "First Amendment to Guaranty Agreement" are
hereby added to Section 1.01 where alphabetically appropriate:

                      "Amended and Restated Confirmation Letter" shall have the
           meaning set forth in Section 2.01(a).

                      "First Amendment" shall mean that certain First Amendment
           to Natural Gas Advance Sale Contract dated as of March 30, 2001
           between Seller and Purchaser.

                                       1
<PAGE>   3
                      "First Amendment to Guaranty Agreement" shall mean that
           certain First Amendment to Guaranty dated as of March 30, 2001
           between Guarantor and Purchaser.

                      (b) The definition of "Confirmation Letter" is hereby
           amended to read as follows:

                      "Confirmation Letter" shall mean that certain Confirmation
           of Natural Gas Advance Sale between Purchaser and Seller executed on
           December 2, 1999.

                      (c) The definition of "Delivery Month" is hereby amended
           to read as follows:

                      "Delivery Month" means each calendar month commencing with
           the month of April, 2002, through and including the month of
           November, 2004; and each calendar month commencing with the month of
           August, 2005, through and including the month of January, 2006.

                      (d) The definition of "Guaranty Agreement" is hereby
           amended to read as follows:

                     "Guaranty Agreement" shall mean that certain Guaranty dated
           of even date herewith given by Guarantor in favor of Purchaser to
           secure the payment and performance obligations of Seller under this
           Agreement and the Confirmation Letter, as set forth therein, as
           amended by the First Amendment to Guaranty, and as the same may be
           amended, modified or replaced from time to time.

           2.2 Other Amendments. The definition of "Agreement" in the
introductory paragraph is hereby amended to read as follows:

                      (as amended by the First Amendment and as the same may be
           further amended from time to time, this "Agreement")

           2.3 Amendment to Section 2.01. Section 2.01(a) is hereby amended to
read as follows:

                     (a) On December 2, 1999, Purchaser and Seller executed the
           Confirmation Letter. On or before March 30, 2001, Purchaser and
           Seller shall agree upon and execute an amended and restated
           Confirmation Letter in substantially the form of Annex 1 attached to
           the First Amendment (the "Amended and Restated Confirmation Letter").
           If on or before March 30, 2001, the Amended and Restated Confirmation
           Letter has not been executed and delivered by the parties hereto,
           then the First Amendment shall terminate and be null and void without
           any further actions by the parties; provided in no event shall the
           failure of the parties to execute the Amended and Restated
           Confirmation Letter affect the rights and obligations of the parties
           with respect to the volumes of Natural Gas sold and to be delivered
           under the Confirmation Letter.

                     The Confirmation Letter specified as of the date thereof
           (i) a mutually acceptable Prepaid Price with respect to the Natural
           Gas to be delivered thereunder, (ii) the date on which the Prepaid
           Price in respect of such Natural Gas was paid, and (iii) for each
           Delivery Month, the Required Delivery Quantity.

                     The Amended and Restated Confirmation Letter shall amend
           and restate the delivery and receipt obligations of the parties under
           the Confirmation Letter, and shall specify for each Delivery Month,
           the Delivery Points (if necessary), the Required

                                       2
<PAGE>   4
           Delivery Quantity, and the amount thereof to be delivered and
           received at each such Delivery Point (if necessary), each as mutually
           agreed by Purchaser and Seller. No additional Prepaid Price or other
           consideration shall be due by Purchaser in connection with the
           execution and delivery of the Amended and Restated Confirmation
           Letter.

           Section 3.Conditions Precedent. The effectiveness of this First
Amendment is subject to the receipt by the Purchaser of the following documents
and satisfaction of the other conditions provided in this Section 3, each of
which shall be satisfactory to the Purchaser in form and substance:

           3.1 Transaction Documents. The Purchaser shall have received multiple
counterparts of each of the following documents, each executed and delivered by
a duly authorized officer of each party thereto:

           (a)       This First Amendment;

           (b)       The Amended and Restated Confirmation Letter;

           (c)       The First Amendment to Guaranty Agreement;

           (d) A certificate of the Secretary or an Assistant Secretary of
Seller setting forth (i) resolutions of its Board of Directors with respect to
the authorization of the Seller to execute and deliver this First Amendment and
the other documents described in Section 3.1(b) - (d) hereof to which it is a
party and to enter into the transactions contemplated in those documents, (ii)
the officers of such Person (y) who are authorized to sign such agreements and
(z) who will, until replaced by another officer or officers duly authorized for
that purpose, act as its representative for the purposes of signing documents in
connection with such agreements and the transactions contemplated hereby, (iii)
specimen signatures of the authorized officers, and (iv) that no change has been
made to its certificate of incorporation and by-laws since December 1, 1999;

           (e) A certificate of the Secretary or an Assistant Secretary of
Guarantor setting forth (i) resolutions of its Board of Directors with respect
to the authorization of the Guarantor to execute and deliver the First Amendment
to Guaranty Agreement and the other documents described in Section 3.1(b) - (d)
hereof to which it is a party and to enter into the transactions contemplated in
those documents, (ii) the officers of such Person (y) who are authorized to sign
such agreements and (z) who will, until replaced by another officer or officers
duly authorized for that purpose, act as its representative for the purposes of
signing documents in connection with such agreements and the transactions
contemplated hereby, (iii) specimen signatures of the authorized officers, and
(iv) that no change has been made to its certificate of incorporation and
by-laws since December 1, 1999; and

           (f) An opinion of in-house counsel to Seller and Guarantor, in form
and substance reasonably satisfactory to the Purchaser.

           3.2 No Event of Default or Event of Change. No Event of Default or
Event of Change shall have occurred and be continuing as of the Effective Date.

           Section 4.Representations and Warranties; Etc. Each party hereby
affirms: (a) that as of the date of execution and delivery of this First
Amendment, all of the representations and warranties contained in each
Transaction Document to which it is a party are true and correct in all material
respects as though made on and as of the Effective Date, and (b) that after
giving effect to this First Amendment

                                       3



                                       1
<PAGE>   5
and to the transactions contemplated hereby, no defaults exist under the
Transaction Documents or will exist under the Transaction Documents.

           Section 5.Miscellaneous.

           5.1 Ratification and Affirmation of Transaction Documents. Each of
the parties hereby expressly (i) acknowledges and agrees to the terms of this
First Amendment, (ii) confirms and ratifies all of its obligations, liabilities
and duties under each of the Transaction Documents to which it is a party as
amended hereby, (iii) acknowledges its continued liability under each of the
Transaction Documents to which it is a party and agrees that each such
Transaction Document shall continue in full force and effect in accordance with
the terms of such Transaction Document as amended hereby.

           5.2 Counterparts. This First Amendment may be executed by one or more
of the parties hereto in any number of separate counterparts, and all of such
counterparts taken together shall be deemed to constitute one and the same
instrument.

           5.3 No Oral Agreement. THIS WRITTEN FIRST AMENDMENT, THE NATURAL GAS
ADVANCE SALE CONTRACT AND THE OTHER TRANSACTION DOCUMENTS EXECUTED IN CONNECTION
HEREWITH AND THEREWITH REPRESENT THE FINAL AGREEMENT BETWEEN THE PARTIES AND MAY
NOT BE CONTRADICTED BY EVIDENCE OF PRIOR, CONTEMPORANEOUS, OR UNWRITTEN ORAL
AGREEMENTS OF THE PARTIES. THERE ARE NO SUBSEQUENT ORAL AGREEMENTS BETWEEN THE
PARTIES.

           5.4 GOVERNING LAW. THIS FIRST AMENDMENT (INCLUDING, BUT NOT LIMITED
TO, THE VALIDITY AND ENFORCEABILITY HEREOF) SHALL BE GOVERNED BY, AND CONSTRUED
IN ACCORDANCE WITH, THE LAWS OF THE STATE OF NEW YORK AND APPLICABLE FEDERAL
LAWS OF THE UNITED STATES OF AMERICA.

                                       4
<PAGE>   6
           IN WITNESS WHEREOF, the parties hereto have caused this First
Amendment to be duly executed effective as of the date first written above.

SELLER:                    COLUMBIA NATURAL RESOURCES, INC.


                           By:_ /s/ R.Neal Pierce_______________
                           Name:_ R.Neal Pierce ___________________
                           Title:___Vice President and Secretary_______________



PURCHASER:                 MAHONIA II LIMITED


                           By:_ /s/ Ian James ________________
                           Name:__ Ian James _________________________
                           Title:Director






[Signature Page - First Amendment to Natural Gas Advance Sale Contract between
Columbia Natural Resources, Inc., as Seller, and Mahonia II Limited, as
Purchaser]
<PAGE>   7
                                     Annex 1

                Form of Amended and Restated Confirmation Letter





                                    Annex 1-1
<PAGE>   8

                              AMENDED AND RESTATED
                    CONFIRMATION OF NATURAL GAS ADVANCE SALE


Columbia Natural Resources, Inc.
900 Pennsylvania Avenue
Charleston, West Virginia  25362-0070


This is to confirm that, under the terms of the Natural Gas Advance Sale
Contract between Columbia Natural Resources, Inc ("CNR") and Mahonia II Limited
("Mahonia") dated as of December 1, 1999 (the "Advance Sale Contract" terms not
defined herein having the meaning therein given), as amended by the First
Amendment To Natural Gas Advance Sale Contract dated as of March 30, 2001, the
following Required Delivery Quantities for each Delivery Month delivered at the
Delivery Point.


NATURAL GAS DELIVERY SCHEDULE:            See attached



MAHONIA II LIMITED

By:  /s/ Ian James

Name:  Ian James

Title: Director


ACCEPTED AND AGREED:
-------------------

COLUMBIA NATURAL RESOURCES, INC.


By:  /s/ Neal Pierce

Name: R. Neal Pierce

Title:  Vice President and Secretary


                                       1
<PAGE>   9
                                       2
<PAGE>   10
               REQUIRED DELIVERY QUANTITY FOR EACH DELIVERY MONTH

<TABLE>
<CAPTION>
                                Required Delivery
                                 Quantity
Delivery Month                   (MMBtu/day)
--------------
<S>                             <C>
February-00                      40,000
March-00                         40,000
April-00                         40,000
May-00                           40,000
June-00                          40,000
July-00                          40,000
August-00                        40,000
September-00                     40,000
October-00                       40,000
November-00                      40,000
December-00                      40,000
January-01                       40,000
February-01                      40,000
March-01                         40,000
April-01                         0
May-01                           0
June-01                          0
July-01                          0
August-01                        0
September-01                     0
October-01                       0
November-01                      0
December-01                      0
January-02                       0
February-02                      0
March-02                         0
April-02                         40,000
May-02                           40,000
June-02                          40,000
July-02                          40,000
August-02                        40,000
September-02                     40,000
October-02                       40,000
November-02                      40,000
December-02                      40,000
January-03                       56,190
February-03                      56,190
March-03                         56,190
April-03                         56,190
May-03                           56,190
June-03                          56,190
July-03                          56,190
</TABLE>


                                       3
<PAGE>   11
<TABLE>
<S>                             <C>
August-03                        56,190
September-03                     56,190
October-03                       56,190
November-03                      56,190
December-03                      56,190
January-04                       56,190
February-04                      56,190
March-04                         56,190
April-04                         56,190
May-04                           56,190
June-04                          56,190
July-04                          56,190
August-04                        56,190
September-04                     46,190
October-04                       46,190
November-04                      16,190
December-04                      16,190
January-05                       0
February-05                      0
March-05                         0
April-05                         0
May-05                           0
June-05                          0
July-05                          0
August-05                        55,048
September-05                     55,048
October-05                       55,048
November-05                      55,048
December-05                      55,048
January-06                       55,048
February-06                      51,162
</TABLE>


                                       4