Parameter tuning in Bayesian networks is the process of adapting network parameters in order to enforce a predefined query response. Existing approaches select and adapt parameters based on their values in the partial derivatives of the query response. This approach is based on the assumption that a minimal change in parameters is preferred. In this paper we argue for including the uncertainty in the current parameter estimates in the selection and adaptation of the parameters. We propose a new evaluation criterion, for networks with binary-valued variables, together with new tuning heuristics that take this higher-order uncertainty into account. We evaluate our proposal and observe in our experiments that two of the proposed heuristics that take this additional uncertainty into account consistently outperform tuning based on gradients alone.