Be smarter about choosing branches

Part of this is also about failing sooner, and not allowing invalid
configurations to enter the queue. This commit also fixes an obscure bug
in substitute_placeholders(). Finally, it adds unit tests for all bugs
fixed.

Signed-off-by: Zack Cerza <zack.cerza@inktank.com>