Paths cannot have leading / character

[abronan]

Reference to the issue in the upstream repository: docker#155

This is still an issue somehow, we should be able to give a key beginning with a / no matter which store we're using, even if we strip this out in the case of Consul because it does not allow keys to start with /.