Document:

<PAGE>

                                                                  EXHIBIT 10.4.1

                            FIRST AMENDMENT TO LEASE

          THIS FIRST AMENDMENT TO LEASE (this "First Amendment") is made and
entered into as of the 13th day of March 2000 by and between VALLEY MEDIA, INC.,
a Delaware corporation ("Tenant"), and BETTY KUHN, an individual ("Landlord").

                                 Recitals

          A.   Pursuant to that Build-to-Suit Facility Absolute Net Lease dated
as of October 3, 1989 (the "Original Lease"), Carl D. Panattoni ("Panattoni")
leased to Pacific Rice Products, Inc., a California corporation ("Pacific"), a
building consisting of approximately 60,000 rentable square feet commonly known
as 1277 Santa Anita Court, Woodland (Yolo County), California, together with
easements for ingress and egress and parking (the "Property"), all as more
particularly described in the Original Lease.

          B.   Panattoni and Pacific modified the Original Lease pursuant to:
(i) that certain Letter Agreement dated as of March 15, 1990 from Panattoni to
Pacific (as approved and accepted by Pacific) (the "Letter Agreement"); (ii)
that certain First Amendment to Absolute Net Lease dated as of November 1990
(the "First Amendment"); and (iii) that certain Second Amendment to Absolute Net
Lease dated as of November 1990 (the "Second Amendment").  The Original Lease,
as modified by the Letter Agreement, the First Amendment and the Second
Amendment, shall be referred to in this Sublease as the "Revised Lease."

          C.   Landlord succeeded to the right, title and interest of Panattoni
under the Revised Lease.  Pacific Grain Rice Products, Inc., a California
corporation ("Grain"), succeeded to the right, title and interest of Pacific
under the Revised Lease.

          D.   Pursuant to that certain Assignment, Assumption and Consent
Agreement dated as of May 9, 1994 (the "Assignment"), Grain assigned to Valley
Record Distributors, Inc., a California corporation ("Record"), all of Grain's
right, title and interest under the Revised Lease.  Record accepted the
assignment and assumed the obligations of the tenant under the Revised Lease
from and after the Effective Date (as defined in the Assignment), and Landlord
consented to the assignment and assumption.

          E.   The Revised Lease, as modified by the Assignment, shall be
referred to in this Sublease as the "Lease."

          F.   Record changed its name to Valley Media, Inc., a California
corporation.  Tenant and Record then merged.

          G.   Tenant is the current holder of all of the right, title and
interest of the tenant under the Lease.  Landlord is the current holder of all
of the right, title and interest of the landlord under the Lease.

          H.   The term of the Lease expires on May 31, 2000.

          I.   Upon the terms and conditions set forth in this First Amendment,
Landlord and Tenant desire to extend the term of the Lease through May 31, 2003
and to make certain other modifications to the Lease.

                         Agreement Terms and Conditions

          NOW, THEREFORE, for good and valuable consideration, the receipt and
sufficiency of which are acknowledged, Landlord and Tenant agree as follows:

          1.   Lease Term.  The expiration of the term of the Lease is hereby
               ----------
extended from May 31, 2000 to May 31, 2003.

                                       1
<PAGE>

          2.   Base Rent.  Tenant shall pay to Landlord Base Rent for the
               ---------
Property in the amount of $19,200.00 per month, fixed for the balance of the
term of the Lease.

          3.   Utilities.  Landlord and Tenant recognize that the Property,
               ---------
together with the facility located at 1275 Santa Anita Court, Woodland (Yolo
County), California (the "South Portion"), are currently part of one large
building (the "Complex").  Within thirty (30) days after the date of this First
Amendment, Tenant shall separate the utilities serving the Property and the
South Portion such that the utilities serving the Property are separately
metered.

          4.   Condition of Property.  Subject to Tenant completing the
               ---------------------
separation of the utilities as specified in the preceding provision, Tenant
shall continue to lease the Property "as-is."

          5.   Roof Access.  Landlord grants to Tenant a non-exclusive easement
               -----------
over the roof of the South Portion for the purpose of placing, running,
operating, maintaining and servicing Tenant's fiber optics, cables, and other
data transmission lines.

          6.   Parking.  Tenant shall be allocated all of the parking spaces for
               -------
the Complex, with the exception of 50 spaces which shall be allotted to the
South Portion.

          7.   Estoppel.  Tenant warrants, represents and certifies to Landlord
               --------
that as of the date of this First Amendment:  (a) Landlord is not in default
under the Lease; and (b) Tenant does not have any defenses or offsets to payment
of rent and performance of its obligations under the Lease as and when same
becomes due.  Landlord warrants, represents and certifies to Tenant that as of
the date of this First Amendment:  (a) Tenant is not in default under the Lease;
and (b) Landlord does not have any defenses to the performance of its
obligations under the Lease as and when the same become due.

          8.   Further Assurances.  In addition to the obligations required to
               ------------------
be performed under the Lease, as amended hereby, Landlord and Tenant each shall
perform such other acts, and shall execute, acknowledge and/or deliver such
other instruments, documents and other materials, as may be reasonably required
in order to accomplish the intent and purpose of the Lease, as amended hereby.

          9.   Attorney's Fees.  In the event either party shall commence an
               ---------------
action to enforce any provision of this First Amendment, the prevailing party in
such action shall be entitled to receive from the other party, in addition to
damages, equitable or other relief, and all costs and expenses incurred,
including reasonable attorneys fees and court costs and the fees and costs of
expert witnesses, and fees incurred to enforce any judgment obtained.  This
provision with respect to attorneys fees incurred to enforce a judgment shall be
severable from all other provisions of this First Amendment, shall survive any
judgment, and shall not be deemed merged into the judgment.

          10.   Brokers.  Each party represents to the other that it has not
                -------
dealt with any broker with respect to this First Amendment.  If a party has
dealt with any broker or person with respect to this First Amendment, that party
shall be solely responsible for the payment of any fees due said person or firm
and that party shall protect, defend, indemnify and hold harmless the other
party from any liability in respect thereto.

          11.   Lease in Full Force.  Except for those provisions which are
                -------------------
inconsistent with this First Amendment and those terms, covenants and conditions
for which performance has heretofore been completed, all other terms, covenants
and conditions of the Lease shall remain in full force and effect. Tenant and
Landlord each ratifies the Lease, as amended hereby.  The term "Lease" where
used in the Lease shall hereinafter refer to the Lease, as amended by this First
Amendment.

          12.   Binding Effect.  This First Amendment shall be binding upon and
                --------------
inure to the benefit of Landlord, its successors and assigns and Tenant and its
successors and assigns.

          13.   Capitalized Terms.  All capitalized terms used herein not
                -----------------
specifically defined in this First Amendment shall have the meanings ascribed to
such terms in the Lease.

          14.   Facsimile.  Each party hereto, and their respective successors
                ---------
and assigns shall be authorized to rely upon the signatures of all of the
parties hereto on this First Amendment which are delivered by facsimile as
constituting a duly authorized, irrevocable, actual, current delivery of this
First Amendment with original ink signatures of each person and entity.

                                       2
<PAGE>

          15.   Condition Precedent.  This First Amendment and the obligations
                -------------------
of Landlord and Tenant are expressly conditioned upon and subject to the full
execution and delivery of that certain Surrender of Lease Agreement dated as of
May 31, 2000 by and between Landlord and Tenant regarding the South Portion.

          16.   Counterparts.  This First Amendment may be executed in
                ------------
counterparts, each of which shall be deemed an original part and all of which
together shall constitute a single agreement.

          IN WITNESS WHEREOF, Landlord and Tenant have executed this First
Amendment as of the date first written above.

LANDLORD:                                      TENANT:

                                               VALLEY MEDIA, INC.,
/s/ Betty Kuhn                                 a Delaware corporation
-----------------------
BETTY KUHN

                                               By: /s/ Paige Dickow
                                                  ----------------------------

                                                Name: Paige S. Dickow
                                                      ----------------------

                                                Position: Senior Vice President
                                                          ---------------------
                                                Organization Effectiveness
                                                --------------------------
                                                and Administration
                                                ------------------

                                       3<PAGE>

                                                                  EXHIBIT 10.5.1

                          SURRENDER OF LEASE AGREEMENT

          THIS SURRENDER OF LEASE AGREEMENT (this "Agreement") is made and
entered into as of the 13th day of March 2000 by and between VALLEY MEDIA, INC.,
a Delaware corporation ("Tenant"), and BETTY KUHN, an individual ("Landlord").

                                 Recitals

          A.   Pursuant to that certain Industrial Real Estate Lease (Multi-
Tenant Facility) dated as of May 21, 1992 (the "Original Lease"), Panattoni
Development Company ("Panattoni") leased to Valley Record Distributors, Inc., a
California corporation ("Record"), a 49,320 square foot portion (the "Property"
or the "Phase I space") of the 109,385 square foot facility located at 1275
Santa Anita Court, Woodland (Yolo County), California (the "Project").

          B.   Panattoni and Record modified the Original Lease pursuant to:
(i) that certain First Amendment to Multi-Tenant Net for Lease dated as of
September 1992 (the "First Amendment"); and (ii) that certain Second Amendment
to Multi-Tenant Net for Lease dated as of July 1993 (the "Second Amendment").
The Original Lease, as modified by the First Amendment and the Second Amendment,
shall be referred to in this Agreement as the "Lease."

          C.   Landlord succeeded to the right, title and interest of Panattoni
under the Lease.  Record changed its name to Valley Media, Inc., a California
corporation.  Tenant and Record then merged.

          D.   Tenant is the current holder of all of the right, title and
interest of the tenant under the Lease.  Landlord is the current holder of all
of the right, title and interest of the landlord under the Lease.

          E.   The term of the Lease expires on May 31, 2003.

          F.   Tenant desires to terminate the Lease and relinquish and
surrender to Landlord the Phase I space.  Landlord desires to permit the
termination of the Lease and to accept Tenant's relinquishment and surrender of
the Phase I space, subject to the terms and conditions set forth in this
Agreement.

                         Agreement Terms and Conditions

          NOW, THEREFORE, for good and valuable consideration, the receipt and
sufficiency of which are acknowledged, Landlord and Tenant agree as follows:

          1.   Termination of Lease.  Subject to Tenant's performance of its
               --------------------
obligations set forth in this Agreement, the Lease shall terminate as of 11:59
p.m. on May 31, 2000 (the "Effective Date"), and Landlord and Tenant shall have
no further duties or obligations to one another in connection with the Lease.
The Lease shall remain in full force and effect up to and including the
Effective Date.

          2.   Surrender of Property.  Tenant shall vacate the Phase I space and
               ---------------------
shall relinquish and surrender possession thereof on or before the Effective
Date.  Landlord shall accept the surrender and relinquishment of the Phase I
space by Tenant.  Landlord and Tenant agree that 50 unmarked parking spaces are
deemed a part of the Property surrendered under this Agreement.

          3.   Discharge of Lease Obligations.  Tenant and Landlord each shall
               ------------------------------
discharge all of its obligations under the Lease up to and including the
Effective Date.

          4.   Restoration of Project.  Landlord and Tenant recognize that the
               ----------------------
Project, together with the facility located at 1277 Santa Anita Court, Woodland
(Yolo County), California (the "North Portion"), are currently part of one large
building (the "Complex").  Within thirty (30) days after the Effective Date:
(i) Tenant shall restore the Phase I space to roughly the same condition as it
existed as of the date of the Second Amendment, reasonable wear and tear and
repairs which are Landlord[]s obligation excepted; (ii) Tenant shall remove or
cause to be removed from the Phase I space all debris and rubbish, furniture,
equipment, business and trade fixtures, and other articles of personal property
owned by Tenant or installed or placed by Tenant at its own expense in the Phase
I

                                       1
<PAGE>

space; (iii) Tenant shall repair all damage to the Phase I space resulting from
the installation and removal of such items to be removed; and (iv) Tenant shall
close the two openings between the Project and the North Portion. Landlord shall
permit Tenant and its agents access to the Project to discharge Tenant's
obligations under this provision.

          5.   Release by Tenant.  As of the Effective Date, Tenant, on behalf
               -----------------
of itself and its predecessors, successors, affiliates and assigns, and all
other persons, firms and corporations claiming through Tenant, and each of them
(collectively, "Tenant Releasing Parties"), releases Landlord and its
predecessors, successors, affiliates and assigns, and their respective partners,
officers, shareholders, agents, contractors, representatives, employees and
attorneys (collectively, "Landlord Released Parties"), of and from any and all
claims, demands, disputes, damages, liabilities, obligations, controversies,
debts, costs, expenses, lawsuits, actions, causes of action and other rights to
relief, both legal and equitable, of every kind and nature, whether now known or
unknown, suspected or unsuspected, past or present, contingent or fixed, which
Tenant Releasing Parties, or any of them, now have, had, or at any time
hereafter may have, against Landlord Released Parties, or any of them, arising
out of or in connection with the Lease, the Property, the Phase I space, the
Project, Tenant's occupancy and possession of the Phase I space, or any dealings
between Landlord Released Parties, or any of them, on the one hand, and Tenant
Releasing Parties, or any of them, on the other hand, with respect to the Lease.
Tenant agrees that this is a general release and expressly waives the protection
of any statute, law, ordinance or regulation, including California Civil Code
Section 1542, or an equivalent law of any jurisdiction, which Tenant
acknowledges and understands provides as follows:

          "A general release does not extend to claims which the creditor does
not know or suspect to exist in his favor at the time of executing the release,
which if known by him must have materially affected his settlement with the
debtor."

          IT IS UNDERSTOOD BY TENANT THAT IF THE FACTS OR LAW WITH RESPECT TO
WHICH THE FOREGOING RELEASE IS GIVEN HEREAFTER TURN OUT TO BE DIFFERENT FROM THE
FACTS OR LAW IN THAT CONNECTION AS BELIEVED BY TENANT TO BE TRUE, THEN TENANT
EXPRESSLY ASSUMES THE RISK OF THE FACTS OR LAW TURNING OUT TO BE SO DIFFERENT
AND AGREES THAT THE FOREGOING RELEASE SHALL BE IN ALL RESPECTS EFFECTIVE AND NOT
SUBJECT TO TERMINATION OR RESCISSION BASED UPON SUCH DIFFERENCES IN FACTS OR
LAW.

          6.   Release by Landlord.  As of the Effective Date, Landlord, on
               -------------------
behalf of itself and its predecessors, successors, affiliates and assigns, and
all other persons, firms and corporations claiming through Landlord, and each of
them (collectively, "Landlord Releasing Parties"), releases Tenant and its
predecessors, successors, affiliates and assigns, and their respective partners,
officers, shareholders, agents, contractors, representatives, employees and
attorneys (collectively, "Tenant Released Parties"), of and from any and all
claims, demands, disputes, damages, liabilities, obligations, controversies,
debts, costs, expenses, lawsuits, actions, causes of action and other rights to
relief, both legal and equitable, of every kind and nature, whether now known or
unknown, suspected or unsuspected, past or present, contingent or fixed, which
Landlord Releasing Parties, or any of them, now have, had, or at any time
hereafter may have, against Tenant Released Parties, or any of them, arising out
of or in connection with the Lease, the Property, the Phase I space, the
Project, Tenant's occupancy and possession of the Phase I space, or any dealings
between Tenant Released Parties, or any of them, on the one hand, and Landlord
Releasing Parties, or any of them, on the other hand, with respect to the Lease.
Landlord agrees that this is a general release and expressly waives the
protection of any statute, law, ordinance or regulation, including California
Civil Code Section 1542, or an equivalent law of any jurisdiction, which
Landlord acknowledges and understands provides as follows:

          "A general release does not extend to claims which the creditor does
not know or suspect to exist in his favor at the time of executing the release,
which if known by him must have materially affected his settlement with the
debtor."

          IT IS UNDERSTOOD BY LANDLORD THAT IF THE FACTS OR LAW WITH RESPECT TO
WHICH THE FOREGOING RELEASE IS GIVEN HEREAFTER TURN OUT TO BE DIFFERENT FROM THE
FACTS OR LAW IN THAT CONNECTION AS BELIEVED BY LANDLORD TO BE TRUE, THEN
LANDLORD EXPRESSLY ASSUMES THE RISK OF THE FACTS OR LAW TURNING OUT TO BE SO
DIFFERENT AND AGREES THAT THE FOREGOING RELEASE SHALL BE IN ALL RESPECTS
EFFECTIVE AND NOT SUBJECT TO TERMINATION OR RESCISSION BASED UPON SUCH
DIFFERENCES IN FACTS OR LAW.

                                       2
<PAGE>

          7.   Governing Law.  This Agreement shall be governed by and construed
               -------------
and enforced in accordance with the laws of the State of California.

          8.   Further Assurances.  Each of the parties hereto agrees to execute
               ------------------
and deliver all such further documents and to take all such further actions as
may be reasonably requested by the other party hereto to effectuate fully the
terms and provisions of this Agreement, provided such documents or actions do
not limit, reduce or impair the rights of the party upon whom such request is
made.

          9.   Binding Agreement.  This Agreement shall be binding upon and
               -----------------
inure to the benefit of the heirs, successors and assigns of the parties hereto.

          10.   Condition Precedent.  This Agreement and the obligations of
                -------------------
Landlord and Tenant are expressly conditioned upon and subject to the full
execution and delivery of that certain First Amendment to Lease dated as of May
31, 2000 by and between Landlord and Tenant regarding the North Portion.

          11.   Counterparts.  This Agreement may be executed in counterparts,
                ------------
each of which shall be deemed an original part and all of which together shall
constitute a single agreement.

          IN WITNESS WHEREOF, Landlord and Tenant have executed this Agreement
as of the date first written above.

LANDLORD:                                      TENANT:

                                               VALLEY MEDIA, INC.,
/s/ Betty Kuhn                                 a Delaware corporation
-----------------------
BETTY KUHN

                                               By: /s/ Paige Dickow
                                                  ----------------------------

                                                Name: Paige S. Dickow
                                                      ----------------------

                                                Position: Senior Vice President
                                                          ---------------------
                                                Organization Effectiveness
                                                --------------------------
                                                and Administration
                                                ------------------

                                       3

Source: [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00010-of-00352.parquet"}, [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00010-of-00352.parquet"}]]