The constrained Cramer-Rao bound (CCRB) is a lower bound on the mean-squared-error (MSE) of estimators that satisfy some unbiasedness conditions. Although the CCRB unbiasedness conditions are satisfied asymptotically by the constrained maximum likelihood (CML) estimator, in the non-asymptotic region these conditions are usually too strict and the commonly-used estimators, such as the CML estimator, do not satisfy them. Therefore, the CCRB may not be a lower bound on the MSE matrix of such estimators. In this paper, we propose a new definition for unbiasedness under constraints, denoted by C-unbiasedness, which is based on using Lehmann-unbiasedness with a weighted MSE (WMSE) risk and taking into account the parametric constraints. In addition to C-unbiasedness, a Cramer-Rao-type bound on the WMSE of C-unbiased estimators, denoted as Lehmann-unbiased CCRB (LU-CCRB), is derived. This bound is a scalar bound that depends on the chosen weighted combination of estimation errors. It is shown that C-unbiasedness is less restrictive than the CCRB unbiasedness conditions. Thus, the set of estimators that satisfy the CCRB unbiasedness conditions is a subset of the set of C-unbiased estimators and the proposed LU-CCRB may be an informative lower bound in cases where the corresponding CCRB is not. In the simulations, we examine linear and nonlinear estimation problems under nonlinear constraints in which the CML estimator is shown to be C-unbiased and the LU-CCRB is an informative lower bound on the WMSE, while the corresponding CCRB on the WMSE is not a lower bound and is not informative in the non-asymptotic region.