In Sharepoint, how do I update the name of a folder in a document library using the web service API?

Question

I'm using the UpdateListItems method of the Lists web service, and I can update an item in just about any kind of list, and folders in non-document library lists, but I can't seem to update the name of a folder in a document library. I must use the web services API, as sharepoint is not local.

If my update batch looks like this:

<Batch OnError="Continue" PreCalc="TRUE" ListVersion="0" ViewName="">
  <Method ID="1" Cmd="Update">
    <Field Name="ID">2</Field>
    <Field Name="Title">MyUpdatedFolderName</Field>
    <Field Name="FileLeafRef">MyUpdatedFolderName</Field>
  </Method>
</Batch>

I get no exception but the name is unchanged.

If my update batch looks like this:

<Batch OnError="Continue" PreCalc="TRUE" ListVersion="0" ViewName="">
  <Method ID="1" Cmd="Update">
    <Field Name="ID">2</Field>
    <Field Name="Title">MyUpdatedFolderName</Field>
    <Field Name="BaseName">MyUpdatedFolderName</Field>
  </Method>
</Batch>

I get an error result that the list item could not be found. I know the list item is there.

Anyone have any ideas?