A few thoughts in response:
I agree with you that if my experience of red can't be constructed of matter, then my understanding of a sentence also can't be. And I agree with you that we don't have a reliable account of how to construct such things out of matter, and without such an account we can't rule out the possibility that, as you suggest, such an account is simply not possible. I agree with you that this objection to physicalism has been around for a long time.
I agree with you that insofar as we understand vitalism to be an account of how particular arrangements of matter move around, it is a different sort of thing from the kind of "sentientism" you are talking about. That said, I think that's a misrepresentation of historical vitalism; I think when the vitalists talked about elan vital being the difference between living and unliving matter, they were also attributing sentience (though not sapience) to elan vital, as well as simple animation.
I don't equate the experience of red with the tendency to output the word "red" when queried, both in the sense that it's easy for me to imagine being unable to generate that output while continuing to experience red, and in the sense that it's easy for me to imagine a system that outputs the word "red" when queried without having an experience of red. Lexicalization is neither necessary nor sufficient for experience.
I don't equate the experience of red with categorization... it is easy to imagine categorization without experience. It's harder to imagine experience without categorization, though. Categorization might be necessary, but it certainly isn't sufficient, for experience.
Like you, I can't come up with a physical account of sentience. I have little faith in the power of my imagination, though. Put another way: it isn't easy for me to see what one can and can't make out of particles. But I agree with you that any such account would be surprising, and that there is a phenomenon there to explain. So I think I fall somewhere in between your two classes of people who are a waste of time to talk to: I get that there's a problem, but it isn't obvious to me that the properties that comprise what it feels like to be a bat must be ontologically basic and nonphysical. Which I think still means I'm wasting your time. (I did warn you in the grandparent comment that you won't find my answer interesting.)
If it turns out that a particular sensation is perfectly correlated with the presence of a particular physical structure, and that disrupting that structure always triggers a disruption of the sensation, and that disrupting the sensation always triggers a disruption of the structure... well, at that point, I'm pretty reluctant to posit a nonphysical sensation. Sure, it might be there, but if I posit it I need to account for why the sensation is so tightly synchronized with the physical structure, and it's not at all clear that that task is any simpler than identifying one with the other, counterintuitive as that may be.
At the other extreme, if the nonphysical structure makes a difference, demonstrating that difference would make me inclined to posit a nonphysical sensation. For example, if we can transmit sensation without transmitting any physical signal, I'd be strongly inclined to posit a nonphysical structure underlying the sensation. Looking for such a demonstrable difference might be a useful way to start getting somewhere.
Perhaps we are closer to mutual understanding than might have been imagined, then. A crucial point: I wouldn't talk about the mind as something "nonphysical". That's why I said that the problem is with our current physical ontology. The problem is not that we have a model of the world in which events outside our heads are causally connected to events inside our heads via a chain of intermediate events. The problem is that when we try to interpret physics ontologically (and not just operationally), the available frameworks are too sparse and palli...
...at least not if you accept a certain line of anthropic argument.
Thomas Nagel famously challenged the philosophical world to come to terms with qualia in his essay "What is it Like to Be a Bat?". Bats, with sensory systems so completely different from those of humans, must have exotic bat qualia that we could never imagine. Even if we deduce all the physical principles behind echolocation, even if we could specify the movement of every atom in a bat's senses and nervous system that represents its knowledge of where an echolocated insect is, we still have no idea what it's like to feel a subjective echolocation quale.
Anthropic reasoning is the idea that you can reason conditioning on your own existence. For example, the Doomsday Argument says that you would be more likely to exist in the present day if the overall number of future humans was medium-sized instead of humongous, therefore since you exist in the present day, there must be only a medium-sized number of future humans, and the apocalypse must be nigh, for values of nigh equal to "within a few hundred years or so".
The Buddhists have a parable to motivate young seekers after enlightenment. They say - there are zillions upon zillions of insects, trillions upon trillions of lesser animals, and only a relative handful of human beings. For a reincarnating soul to be born as a human being, then, is a rare and precious gift, and an opportunity that should be seized with great enthusiasm, as it will be endless eons before it comes around again.
Whatever one thinks of reincarnation, the parable raises an interesting point. Considering the vast number of non-human animals compared to humans, the probability of being a human is vanishingly low. Therefore, chances are that if I could be an animal, I would be. This makes a strong anthropic argument that it is impossible for me to be an animal.
The phrase "for me to be an animal" may sound nonsensical, but "why am I me, rather than an animal?" is not obviously sillier than "why am I me, rather than a person from the far future?". If the doomsday argument is sufficient to prove that some catastrophe is preventing me from being one of a trillion spacefaring citizens of the colonized galaxy, this argument hints that something is preventing me from being one of a trillion bats or birds or insects.
And this could be that animals lack subjective experience. This would explain quite nicely why I'm not an animal: because you can't be an animal, any more than you can be a toaster. So Thomas Nagel can stop worrying about what it's like to be a bat, and the rest of us can eat veal and foie gras guilt-free.
But before we break out the dolphin sausages - this is a pretty weird conclusion. It suggests there's a qualitative and discontinuous difference between the nervous system of other beings and our own, not just in what capacities they have but in the way they cause experience. It should make dualists a little bit happier and materialists a little bit more confused (though it's far from knockout proof of either).
The most significant objection I can think of is that it is significant not that we are beings with experiences, but that we know we are beings with experiences and can self-identify as conscious - a distinction that applies only to humans and maybe to some species like apes and dolphins who are rare enough not to throw off the numbers. But why can't we use the reference class of conscious beings if we want to? One might as well consider it significant only that we are beings who make anthropic arguments, and imagine there will be no Doomsday but that anthropic reasoning will fall out of favor in a few decades.
But I still don't fully accept this argument, and I'd be pretty happy if someone could find a more substantial flaw in it.