Ok, the API there is weird, and the documentation is not very clear. Here is what I have figured out. First time you upload an attachment, you do it through UploadAttachment method, but on the follow-up attempts, you need to call Update. Here's the code that does it:
class AttachmentUploader(object):
  """Uploads a given attachment to a given filecabinet in Google Sites."""
  def __init__(self, site, username, password):
    self.client = gdata.sites.client.SitesClient(
        source="uploaderScript", site=site)
    self.client.ssl = True
    try:
      self.client.ClientLogin(username, password, "some.key")
    except:
      traceback.print_exc()
      raise
  def FindAttachment(self, title):
    uri = "%s?kind=%s" % (self.client.MakeContentFeedUri(), "attachment")
    feed = self.client.GetContentFeed(uri=uri)
    for entry in feed.entry:
      if entry.title.text == title:
        return entry
    return None
  def FindCabinet(self, title):
    uri = "%s?kind=%s" % (self.client.MakeContentFeedUri(), "filecabinet")
    feed = self.client.GetContentFeed(uri=uri)
    for entry in feed.entry:
      if entry.title.text == title:
        return entry
    return None
  def Upload(self, cabinet_title, title, file_path, description):
    """Upload the given file as attachment."""
    ms = gdata.data.MediaSource(file_path=file_path, content_type="text/ascii")
    existing_attachment = self.FindAttachment(title)
    if existing_attachment is not None:
      existing_attachment.summary.text = description
      updated = self.client.Update(existing_attachment, media_source=ms)
      print "Updated: ", updated.GetAlternateLink().href
    else:
      cabinet = self.FindCabinet(cabinet_title)
      if cabinet is None:
        print "OUCH: cabinet %s does not exist" % cabinet_title
        return
      attachment = self.client.UploadAttachment(
          ms, cabinet, title=title, description=description)
      print "Uploaded: ", attachment.GetAlternateLink().href