When does the nuclear norm fail to minimize rank?

Given $F$ and $G$, I'm solving the following problem:

\begin{align} \min_{t} & \quad \mbox{rank}(A) \\ \text{s.t.}& \quad A = \text{diag}(t) F - G \\ \end{align}

I used the nuclear norm, $\|A\|_*$, as a surrogate of the rank, and tried to solve the problem with ADMM. But in the cases when I know the ground truth matrix $\hat{A}$ with a small rank, ADMM outputs a matrix $A$ with $\|A\|_* < \|\hat{A}\|_*$ but $\mbox{rank}(A) \gg \mbox{rank}(\hat{A})$.

Is this a case that the nuclear norm heuristic doesn't work? What should we do when there is a matrix with a smaller nuclear norm but with a greater rank?