In LR 4.1 (under Win7 64-bit), I can filter a smart collection by stars. But when I try to filter by color, no image is returned. Maybe this is a limitation of smart collections that I don't know about, but that would be strange since filtering by stars works just fine.
Right - I don't have it as a criteria in the screenshot. Once I display the smart collection, filtering works by stars but not by color label. To get around this, I updated the smart collection definition and essentially created two smart collections, one in which I filter for red selected, and the other for no red selected.
North America
Europe, Middle East and Africa
Asia Pacific