The word counterintuitive literally means counter to intuition, and so it essentially means that something does not seem right or correct.
A counterintuitive proposition is one that does not seem likely to be true when assessed using intuition or gut feelings.
Scientifically discovered, objective truths are often called counterintuitive when intuition, emotions, and other cognitive processes outside of deductive rationality interpret them to be wrong. However, the subjective nature of intuition limits the objectivity of what to call counterintuitive because what is counter-intuitive for one may be intuitive for another. This might occur in instances where intuition changes with knowledge. For instance, many aspects of quantum mechanics may sound counterintuitive to a layman, while they may be intuitive to a particle physicist.
Flawed understanding of a problem may lead to counter-productive behaviour with undesirable outcomes. In some such cases, counterintuitive policies may then produce a more desirable outcome. For example, a policy of catching large fish and throwing back small ones may be counter-productive. In response to that policy, evolutionary pressure may select for small fish. A counterintuitive improvement may be to catch only medium sized fish, leaving the biggest free to breed, creating evolutionary pressure for fish to grow quickly through the medium size.