Fix CheckDeps for not found

* When a dependency was not found, it wasn't being listed as one per
  line as it should have been. That was fixed by adding \\ in the sed
  command.
* The other change here is we basically only try more when it's Linux
  and give up if the command isn't in the PATH on other systems.