I just tried still the same problem.
I ran bowtie2 to test, again I saw samtools come up on top, but same error:
Traceback (most recent call last):
  File "/home/galaxy/galaxy-dist/lib/galaxy/jobs/runners/local.py", line 129, in queue_job
    job_wrapper.finish( stdout, stderr, exit_code )
  File "/home/galaxy/galaxy-dist/lib/galaxy/jobs/__init__.py", line 998, in finish
    dataset.datatype.set_meta( dataset, overwrite=False )  # call datatype.set_meta directly for the initial set_meta call during dataset creation
  File "/home/galaxy/galaxy-dist/lib/galaxy/datatypes/binary.py", line 251, in set_meta
    raise Exception, "Error Setting BAM Metadata: %s" % stderr
Exception: Error Setting BAM Metadata: /bin/sh: samtools: command not found