I hope you still see this. I don't know a specific term for the exact kind of problem you mentioned. However, I would think that it can be explained by linguistic as well as cognitive or memory processes. Hence, my proposed explanation comes in two parts.
One view would be that it has to do with how we interpret language, specifically that we usually try to avoid irrelevant information. A classic in pragmatics (the field of linguistics that deals with how we actually use language to achieve things - make someone understand something, request things, or pose riddles) is the work by Paul Grice (1975).
Grice posited that we usually try to communicate cooperatively, i.e. in such a manner that it is easy for our communication partner to understand what we are saying. He said that we usually adhere to four conversational maxims: information (say as much but not more than is required for understanding the message), truth (say what you think is true), relation (be relevant), and manner (be clear and brief).
The important part is that, when trying to understand what someone has said, we also assume that the other is also following that rule. So when you say the cowboy thing, we usually assume that it's informative, relevant, and true and base all our interpretations and deliberations on that. This essentially means that to understand a statement you have to accept it as true. (Actually, Grice has fallen a bit out of favour with linguists, but newer accounts like relevance theory would lead to roughly the same conclusion.)
But that would not explain why that should still be the case after you tell the guesser that the information is actually irrelevant. This can likely be explained by the way memory works. A good start on this is the article by Lewandowsky and colleagues (2012). As soon as we get some information, we connect it to other information that is also currently relevant in our memory. That means that as soon as you say that the man is a cowboy, he is one in our memory. We connect the man (which was before just a non-descript man in a bar) with our mental concept of a cowboy. These connections get stronger the more they are used.
Your assertion that he actually wasn't a cowboy doesn't delete that connection, it likely only adds a "NOT" tag to it, but the connection itself is still there and has actually been strengthened further by the repeated mention. What is more, you do not provide an alternative (e.g., he's a truck driver or whatever) which could have lead to another, competing connection. To actually consider that "NOT" connection is effortful and strengthens the man--cowboy connection even further. Research usually calls this the misinformation effect or continued influence of misinformation.
Hope this helps! If someone with a better grip on pragmatics and/or memory processes is willing to correct (ha!) my explanation, I'd appreciate it.
Grice, H. P. (1975). Logic and conversation. In P. Cole & J. Morgan (Eds.), Syntax and semantics (Vol. 3). New York, NY: Academic Press.
Lewandowsky, S., Ecker, U. K. H., Seifert, C. M., Schwarz, N., & Cook, J. (2012) Misinformation and its correction: continued influence and successful debiasing. Psychological Science in the Public Interest (13). doi:10.1177/1529100612451018