One reason agents will get that message is if the Master and Distributed Repositories are out of sync.
I've seen this issue in my environment when changes have been made to the Master Repository without those changes being replicated to the Distributed Repositories straight away (eg. checking in extra.dats and not kicking off a replicate to distributed repositories task immediately).
Oddly enough the problem resolved itself, I did nothing. This does happen frequently though.
When I experience issues like this, DNS seems to be the cause. So...ensure DNS is functioning properly.
In some cases, I add the ePO servers and distributed repositories to the hosts file on the client-node. This seems to clear the issue and I have not dug any further to see if there is another cause.
Hope that helps.