Exhibit 4.3

Exhibit 4.3

AMENDMENT NO. 1

TO

THIRD AMENDED AND RESTATED

AGREEMENT OF LIMITED PARTNERSHIP

OF

VALERO L.P.

This Amendment No.1, dated as of March 11, 2004 (this “Amendment”), to the Third Amended and Restated Agreement of Limited Partnership of Valero L.P. (the “Partnership Agreement”), is entered into by and among Riverwalk Logistics L.P., a Delaware limited partnership, as the General Partner, and the Limited Partners as provided herein. Each capitalized term used but not otherwise defined herein shall have the meaning assigned to such term in the Partnership Agreement.

W  I  T  N  E  S  S  E  T  H:

WHEREAS, Section 13.1(d) of the Partnership Agreement provides that the General Partner, without the approval of any Partner, may amend any provision of the Partnership Agreement to reflect a change that, in the discretion of the General Partner, does not adversely affect the Limited Partners in any material respect; and

WHEREAS, the General Partner deems it in the best interest of the Partnership to effect this Amendment in order to reduce the highest level of Incentive Distributions under the Partnership Agreement from 48% to 23%;

WHEREAS, the General Partner deems it in the best interest of the Partnership to further amend the Partnership Agreement to provide that the General Partner may be removed by the vote of at least a Unit Majority (excluding the Common Units and Subordinated Units held by the General Partner and its Affiliates);

WHEREAS, the General Partner, as the sole general partner, on behalf of itself and the Limited Partners, now desires to, and hereby does, amend the Partnership Agreement to reflect such amendments; and

WHEREAS, the Board of Directors of Valero GP, LLC, the general partner of the General Partner, approved this Amendment effective as of March 4, 2004;

NOW, THEREFORE, the Partnership Agreement is hereby amended as follows:

Section 1.1 is hereby amended to delete the definitions of “Second Liquidation Target Amount” and “Second Target Distribution”, and the definition of “Incentive Distributions” is hereby amended to delete the references to Section 6.4(a)(vi) and Section 6.4(b)(iv).

1. Section 6.1(c)(i) is hereby amended to read in its entirety as follows:

(i) If a Net Termination Gain is recognized (or deemed recognized pursuant to Section 5.5(d)), such Net Termination Gain shall be allocated among the General Partner and the Limited Partners in the following manner (and the Capital Accounts of the Partners shall be increased by the amount so allocated in each of the following subclauses, in the order listed, before an allocation is made pursuant to the next succeeding subclause):

(A) First, to each Partner having a deficit balance in its Capital Account, in the proportion that such deficit balance bears to the total deficit balances in the Capital Accounts of all Partners, until each such Partner has been allocated Net Termination Gain equal to any such deficit balance in its Capital Account;

(B) Second, 98% to all Unitholders holding Common Units, Pro Rata, and 2% to the General Partner until the Capital Account in respect of each Common Unit then Outstanding is equal to the sum of (1) its Unrecovered Capital plus (2) the Minimum Quarterly Distribution for the Quarter during which the Liquidation Date occurs, reduced by any distribution pursuant to Section 6.4(a)(i) or (b)(i) with respect to such Common Unit for such Quarter (the amount determined pursuant to this clause (2) is hereinafter defined as the “Unpaid MQD”), plus (3) any then existing Cumulative Common Unit Arrearage;

(C) Third, if such Net Termination Gain is recognized (or is deemed to be recognized) prior to the expiration of the Subordination Period, 98% to all Unitholders holding Subordinated Units, Pro Rata, and 2% to the General Partner until the Capital Account in respect of each Subordinated Unit then Outstanding equals the sum of (1) its Unrecovered Capital, determined for the taxable year (or portion thereof) to which this allocation of gain relates, plus (2) the Minimum Quarterly Distribution for the Quarter during which the Liquidation Date occurs, reduced by any distribution pursuant to Section 6.4(a)(iii) with respect to such Subordinated Unit for such Quarter;

(D) Fourth, 90% to all Unitholders, Pro Rata, 8% to the holders of the Incentive Distribution Rights, Pro Rata, and 2% to the General Partner until the Capital Account in respect of each Common Unit then Outstanding is equal to the sum of (1) its Unrecovered Capital, plus (2) the Unpaid MQD, plus (3) any then existing Cumulative Common Unit Arrearage, plus (4) the excess of (aa) the First Target Distribution less the Minimum Quarterly Distribution for each Quarter of the Partnership’s existence over (bb) the cumulative per Unit amount of any distributions of Operating Surplus that was distributed pursuant to Sections 6.4(a)(iv) and 6.4(b)(ii) (the sum of (1) plus (2) plus (3) plus (4) is hereinafter defined as the “First Liquidation Target Amount”); and

(E) Finally, any remaining amount 75% to all Unitholders, Pro Rata, 23% to the holders of the Incentive Distribution Rights, Pro Rata, and 2% to the General Partner.

2

2. Section 6.4 is hereby amended to read in its entirety as follows:

(a) During Subordination Period. Available Cash with respect to any Quarter within the Subordination Period that is deemed to be Operating Surplus pursuant to the provisions of Section 6.3 or 6.5 shall, subject to Section 17-607 of the Delaware Act, be distributed as follows, except as otherwise required by Section 5.6(b) in respect of additional Partnership Securities issued pursuant thereto:

(i) First, 98% to the Unitholders holding Common Units, Pro Rata, and 2% to the General Partner until there has been distributed in respect of each Common Unit then Outstanding an amount equal to the Minimum Quarterly Distribution for such Quarter;

(ii) Second, 98% to the Unitholders holding Common Units, Pro Rata, and 2% to the General Partner until there has been distributed in respect of each Common Unit then Outstanding an amount equal to the Cumulative Common Unit Arrearage existing with respect to such Quarter;

(iii) Third, 98% to the Unitholders holding Subordinated Units, Pro Rata, and 2% to the General Partner until there has been distributed in respect of each Subordinated Unit then Outstanding an amount equal to the Minimum Quarterly Distribution for such Quarter;

(iv) Fourth, 90% to all Unitholders, Pro Rata, 8% to the holders of Incentive Distribution Rights, Pro Rata, and 2% to the General Partner until there has been distributed in respect of each Unit then Outstanding an amount equal to the excess of the First Target Distribution over the Minimum Quarterly Distribution for such Quarter; and

(v) Thereafter, 75% to all Unitholders, Pro Rata, 23% to the holders of Incentive Distribution Rights, Pro Rata, and 2% to the General Partner;

provided, however, if the Minimum Quarterly Distribution and the First Target Distribution have been reduced to zero pursuant to the second sentence of Section 6.6(a), the distribution of Available Cash that is deemed to be Operating Surplus with respect to any Quarter will be made solely in accordance with Section 6.4(a)(v).

(b) After Subordination Period. Available Cash with respect to any Quarter after the Subordination Period that is deemed to be Operating Surplus pursuant to the provisions of Section 6.3 or 6.5, subject to Section 17-607 of the Delaware Act, shall be distributed as follows, except as otherwise required by Section 5.6(b) in respect of additional Partnership Securities issued pursuant thereto:

(i) First, 98% to all Unitholders, Pro Rata, and 2% to the General Partner until there has been distributed in respect of each Unit then Outstanding an amount equal to the Minimum Quarterly Distribution for such Quarter;

(ii) Second, 90% to all Unitholders, Pro Rata, 8% to the holders of Incentive Distribution Rights, Pro Rata, and 2% to the General Partner until there has

3

been distributed in respect of each such Unit then Outstanding an amount equal to the excess of the First Target Distribution over the Minimum Quarterly Distribution for such Quarter;

(iii) Thereafter, 75% to all Unitholders, Pro Rata, 23% to the holders of Incentive Distribution Rights, Pro Rata, and 2% to the General Partner;

provided, however, if the Minimum Quarterly Distribution and the First Target Distribution have been reduced to zero pursuant to the second sentence of Section 6.6(a), the distribution of Available Cash that is deemed to be Operating Surplus with respect to any Quarter will be made solely in accordance with Section 6.4(b)(iii).

3. Section 6.6(a) is hereby amended to delete the references to the Second Target Distribution.

4. Section 6.6(b) is hereby amended to delete the reference to the Second Target Distribution.

5. Section 6.9 is hereby amended to delete the reference to the Second Target Distribution.

6. Section 11.2 is hereby amended to read in its entirety as follows:

SECTION 11.2 Removal of the General Partner

The General Partner may be removed if such removal is approved by the Unitholders holding at least a Unit Majority (excluding Units held by the General Partner and its Affiliates). Any such action by such holders for removal of the General Partner must also provide for the election of a successor General Partner by the Unitholders holding a Unit Majority (excluding Units held by the General Partner and its Affiliates). Such removal shall be effective immediately following the admission of a successor General Partner pursuant to Section 10.3. The removal of the General Partner shall also automatically constitute the removal of the General Partner as general partner of the other Group Members of which the General Partner is a general partner, if any. If a Person is elected as a successor General Partner in accordance with the terms of this Section 11.2, such Person shall, upon admission pursuant to Section 10.3, automatically become a successor general partner of the other Group Members of which the General Partner is a general partner. The right of the holders of Outstanding Units to remove the General Partner shall not exist or be exercised unless the Partnership has received an opinion opining as to the matters covered by a Withdrawal Opinion of Counsel. Any successor General Partner elected in accordance with the terms of this Section 11.2 shall be subject to the provisions of Section 10.3.

As amended hereby, the Partnership Agreement is in all respects ratified, confirmed and approved and shall remain in full force and effect.

4

IN WITNESS WHEREOF, the parties hereto have executed this Agreement as of the date first written above.

5