On further inspection I think this is because I managed to name the package repository TravelingSalesmanHeuristics.jl (rather than just TravelingSalesmanHeuristics). Indeed I just ran Pkg.add("TravelingSalesmanHeuristics") and now have in my .julia/v0.4 both TravelingSalesmanHeuristics and TravelingSalesmanHeuristics.jl
When I published v0.0.1 Pkg.publish failed (different error, can't remember) and I had to create the pull request manually; presumably I now have to do that going forward?