Comment 3 for bug 518070

-cli and -gtk are no different in that regard, they use the same checks. The most plausible cause is that right after an install you need to refresh the package list. If you wait a day, then it gets refreshed automatically; you can also start synaptic and use the refresh button.

Does it work after that?