For those that hold that qualia exist, the problem it poses is that of one hand being something whose existence is certain, and the other hand being something that can't submit to any empirical (and therefore scientific) analysis. Qualia are non-amenable to empirical investigation because a scientist can never adopt the first person perspective of different person. Thomas Nagel describes the problem in his paper "What's it like to be a bat" (Nagel, Thomas (1974). The Philosophical Review 83 (4): 435–450.):
We may call this the subjective character of experience. It is not captured by any of the familiar, recently devised reductive analyses of the mental, for all of them are logically compatible with its absence. It is not analyzable in terms of any explanatory system of functional states, or intentional states, since these could be ascribed to robots or automata that behaved like people though they experienced nothing.
He then goes on to provide an extreme example to support his position: We can never know what a it is "like" to be bat. Bats are highly evolved mammals with complex brains, and therefore must have subjective experience. But instead of vision, they use echolocation, so their subjective experience will be radically different from ours. We can conceptually understand how a bat moves using sonar, and we can try to imagine ourselves as bats, but we are still using our own subjective experience to "translate" the bat's sense experience in to ours. Ultimately, no matter how hard we try to imagine ourselves as bats, we inevitably imagine the cave they navigate and the insects they catch as visual perceptions, not sonar echoes. Navigating the world through sonar instead of vision is something that is forever inaccessible to us. To quote Nagel's paper again:
It will not help to try to imagine that one has webbing on one's arms, which enables one to fly around at dusk and dawn catching insects in one's mouth; that one has very poor vision, and perceives the surrounding world by a system of reflected high-frequency sound signals; and that one spends the day hanging upside down by one's feet in an attic. In so far as I can imagine this (which is not very far), it tells me only what it would be like for me to behave as a bat behaves. But that is not the question. I want to know what it is like for a bat to be a bat. Yet if I try to imagine this, I am restricted to the resources of my own mind, and those resources are inadequate to the task. I cannot perform it either by imagining additions to my present experience, or by imagining segments gradually subtracted from it, or by imagining some combination of additions, subtractions, and modifications.
David Chalmers described this as the "Hard Problem of Consciousness" (Chalmers, David (1995). "Facing Up to the Problem of Consciousness". Journal of Consciousness Studies 2 (3): 200–219.):
It is undeniable that some organisms are subjects of experience. But the question of how it is that these systems are subjects of experience is perplexing. Why is it that when our cognitive systems engage in visual and auditory information-processing, we have visual or auditory experience: the quality of deep blue, the sensation of middle C? How can we explain why there is something it is like to entertain a mental image, or to experience an emotion? It is widely agreed that experience arises from a physical basis, but we have no good explanation of why and how it so arises. Why should physical processing give rise to a rich inner life at all? It seems objectively unreasonable that it should, and yet it does.
To answer your second question, Daniel Dennett attempts to prove that qualia are a pseudo-problem in his paper "Quining Qualia" (Dennett, Daniel C., In "Consciousness in Modern Science" Anthony J. Marcel & E. Bisiach (eds.), [Book Chapter]. Oxford University Press (1988)) and later in his book "Consciousness Explained".
Supporters say that qualia's special epistemic status comes from the infallibility of our direct knowledge of them, and that they are intrinsic absolute truths: after Descartes, when I see red, I am certain that I see red, the cause of my seeing red is subject to all sorts of doubt (is it reality? illusion? neural damage? etc...), but that I see red is an indisputable fact. But per Dennett, our knowledge of qualia is just as fallible as our knowledge of everything else. Through a series of what he calls intuition pumps, he challenges the infallibility of our knowledge of qualia, and the idea that they are intrinsic experiences that are independent of our memories of past experience and our responses and beliefs to them. From the paper:
I reply: it all depends on what "qualitative or phenomenal" comes to. Shoemaker contrasts qualitative similarity and difference with "intentional" similarity and difference-- similarity and difference of the properties an experience repre sents or is "of". That is clear enough, but what then of "phenomenal"? Among the non-intentional (and hence qualitative?) properties of my visual states are their physiological properties. Might these very properties be the qualia Shoemaker speaks of? It is supposed to be obvious, I take it, that these sorts of features are ruled out, because they are not "accessible to introspection" (Shoemaker, private correspondence). These are features of my visual state, perhaps, but not of my visual experience. They are not phenomenal properties.
