Interesting. I've lived in CA, AZ, Eastern WA, and ID and they're a standard. I've driven in most Western states - I'm thinking of OR, CO, NV, UT, etc. - and haven't noticed their absence.
In any case, where they ARE used they've been around a while yet people just stare stupidly at them. What, do they think they're just decorations? Traffic signals that are facing your lane of traffic *mean something*. This is not a huge intuitive leap, as you mentioned.