There is an unclear relationship between classical conceptions of a unitary view of mental workload to the modern constructs of cognitive psychology and neuroscience that are relevant to your question. This is partly because mental workload is tough to define, and also because it is far too coarse a construct given the extremely large variety of dynamic cognitive factors that play a role in determining human performance. Hopefully this will become clear in the following description.
There is clearly difficulty incurred when one must pick just one option among many, without further guidance, as in your example. Recent work (Snyder et al., PNAS 2010) indicates this kind of difficulty arises from at least two isolable sources: the relative prepotency of the various colors (e.g., the problem is easier if you have a single favorite color, and harder if you like all colors equally) and the total option space (e.g., easier if you only have 3 colors of paint to choose from, harder if you have 500). These seem to have distinct and roughly additive effects on reaction time, at least in speeded lexical tasks, suggesting they both contribute to what you might call "mental workload."
This "underdetermined selection" problem can be made somewhat easier when additional criteria are specified, but not all criteria are equal. "Not green" and "Not bright" are simple cues but are obviously less effective than "blue" or "0 0 255," both because they fail to reduce the problem space as effectively, and because they directly specify distracting information (the colors you're NOT supposed to pick), which will slow visual search processes (e.g., Kiyonaga, Egner & Soto, 2012). Other cues - e.g., "something that goes well with the carpet" - may be more effective at reducing the problem space but probably incur additional mental workload, due to requiring what's known as relational reasoning. There is also clearly a further "working memory load" incurred by the need to simultaneously consider many criteria in selecting the correct paint color.
To the extent that the number of rules given to you exceeds your working memory capacity, you may chose to store those rules in what's sometimes known as secondary memory (e.g., Unsworth & Engle, Psych Review 2007). According to some conceptions of working memory (e.g., Oberauer et al Psychonomic Bulletin & Review, 2012), these items will then fall outside of the so-called "region of direct access," meaning that there are reaction time costs to retrieving these rules. Moreover, maintaining the intention to retrieve those rules at a later point - say, after processing those that do currently occupy your working memory - may itself add a cost to reaction time (e.g., Einstein, et al JEP:G 2005). There are also further "focus switching" costs (Oberauer, 2003) incurred when moving the single focus of attention to each of the rules that fall within the region of direct access.
If these rules are being provided during the "paint search task," they would also probably exert additional costs on reaction time. This again is probably due to multiple sources of interference. One of these likely reflects what's known as dual task costs - you're simultaneously listening to your wife while also trying to find the relevant paint color, and either resource sharing or rapid switching among tasks must occur. On the other hand, even if these rules are provided soon after some other external event in this paint search task, you may also be substantially more delayed in acting upon them (this is known as the "psychological refractory period" effect).
As if that weren't enough, as recently demonstrated by Scalf, Dux & Marois (JoCN, 2011), encoding of information into working memory yields delays in top-down attention in visual cortex.
And finally, under conditions of high working memory load, perceptual selection processes operate less efficiently (e.g., Lavie et al JEP:G 2004), further exacerbating any of the above deleterious effects on your ability to rapidly choose an appropriate paint color from those in front of you.
References
- Einstein, G.O., McDaniel, M.A., Thomas, R., Mayfield, S., Shank, H., Morrisette, N. & Breneiser, J. (2005). Multiple processes in prospective memory retrieval: factors determining monitoring versus spontaneous retrieval.. Journal of Experimental Psychology: General, 134, 327. PDF
- Lavie, N., Hirst, A., de Fockert, J.W. & Viding, E. (2004). Load theory of selective attention and cognitive control.. Journal of Experimental Psychology: General; Journal of Experimental Psychology: General, 133, 339.
- Kiyonaga, A., Egner, T. & Soto, D. (2012). Cognitive control over working memory biases of selection. Psychonomic Bulletin & Review, , 1-8.
- Oberauer, K. (2003) Selective attention to elements in working memory. Experimental Psychology, 257-269.
- Oberauer, K., Lewandowsky, S., Farrell, S., Jarrold, C. & Greaves, M. (2012). Modeling working memory: An interference model of complex span. Psychonomic Bulletin & Review, , 1-41.
- Scalf, P.E., Dux, P.E. & Marois, R. (2011). Working Memory Encoding Delays Top--Down Attention to Visual Cortex. Journal of Cognitive Neuroscience, 23, 2593-2604.
- Snyder, H. R., Hutchinson, N., Nyhus, E., Curran, T., Banich, M. T., O'Reilly, R. C. & Munakata, Y. (2010). Neural inhibition enables selection during language processing. Proceedings of the National Academy of Sciences, 107, 155-167.
- Unsworth, N. & Engle, R.W. (2007). The nature of individual differences in working memory capacity: active maintenance in primary memory and controlled search from secondary memory.. Psychological review, 114, 104. PDF
