1. My position on apriori cognitive categories is close to that of Emile Durkheim (who I believe proposed this solution for the first time) and Noam Chomsky. The capacity of potential to develop and apply categories is innate or genetic, while the specific manifestations of these categories are determined by the structure of social organization and language.
Recent advances in neuro science suggest that experience can affect the structure of thebrain and some cognitive scientists (e.g. Lakoff) acknowledge that. The implications of that is that a particular form of categorization may not be unlearned as easily as some may hope - which has obvious implications for those who hope to replace "bourgeois" categories (false consciousness) with the "proletarian" ones.
2. I am not sure what you arguing regarding the validity of abstract concepts. Obviously, abstract concept not always need empirical verification that 2+2=4 is true even if no 4 objects of a particular kind could be found. The usefulness of such abstract concepts may come in their ability to generate empirical propositions - but I do not think that the concept of class is of that kind. The concept of class is not very abstract, it is an empirical concept whose validity is limited to one particular social-historical situation, but may not be applicable to other situations. This is the same order of abstraction as, say, types of ownership (public, private) it may be useful in the US today, but was not very useful in, say, the USSR in the 1950s.
3. The fact that certain concepts "fail" to bring the desired empirical results (as your discussion on the game theory seems to suggest) may be due to two very different factors: the shortcomings of the concept itself (i.e. lack of clarity, fuzziness, lack of consistency, lack of empirical meaning, etc.) and the shortcomings of the application of the concept (i.e. applying propositions involving the concept outside the scope conditions, or failing to specify such scope conditions at all). The failures of game theories you mention (and the rat choice model in general) seem to be due mainly to the second factor. The problems with the class-based analysis, I believe, is of the first kind - the notion is too vague to be useful, and resolving that vagueness usually result sin such high level of abstraction that it borders on triviality.
To illustrate - if the fact of selling labor is important to defining class, why the kind of labor being sold or conditions of that sale should not matter? Do people selling manual and mental labor belong to different classes or the same class, and why? How about doing different types of mental work (say computer programming and teaching sociology)? Furthermore, does the place where the labor is being sold matter? Does the person selling his labour power to a government owned organization belongs to a different class that one selling his labor power to a private firm? How about the same but in China rather than the US?
4. You sate that classes are products of different relations of production - which at one level is tautological or true by definition - just like "unicorns are horses with one horn growing out of their foreheads" - true but empirically empty. If you want to apply that statement to specific socio-historical conditions you need to explain the process by which relations of production produce classes.
As I previously argued, the notion that capitalist relations of production "produced" the class of people labeled as "working class" - that notion is historically inaccurate. There is plenty of scholarship suggesting that "working class" of the 18th or 19th centuries was in fact a product of the feudal relations - capitalism simply found a certain use for this class. Further more, "capitalism" (i.e. industrialization) profoundly changed the nature of that original working class by differentiating it beyond anything recognizable. So what capitalist relations of production actually produced was not the working class it initially exploited (that was the product of agrarian relations) but the middle "yuppie" class - skilled and while collar workers.
To summarize I think that the usefulness of the concept of class as used by Marx was confined to a particular time and a particular place - and attempts to use it in a different or a broader setting are doomed to produced either trivial tautologies or empirical falsehoods - which btw is true of much of classical and neo-classical economic theorizing of which Marx is an offspring.
Wojtek