Turns out there is a reason for this odd behavior.

A Kernel developer told me,

====

Symbolic computation functions treat expressions with head Equal

as numeric equations and consider non-numeric expressions that

appear in equations as symbolic parameters, even if those

expressions are strings, pictures, Boolean constants, etc.

In[5]:= Solve[x=="Yes" && x+y==Graphics[Circle[]] && x z==True, {x, y, z}]

True

Out[5]= {{x -> Yes, y -> -Yes + -Graphics-, z -> ----}}

Yes

====

Making PiecewiseExpand, Solve, etc, look inside expressions with "==" for non-numerical items

opens up a large box of special cases and potential conflicts.

In your example, using (Full)Simplify on the PiecewiseExpand output is probably the easiest workaround.

There are things one could do with Hold or HoldForm. There isn't a StringEquals function, but StringMatchQ

could be used if keeping strings from being treated as parameters is critical.

In[1]:= $Version

Out[1]= 9.0 for Mac OS X x86 (64-bit) (January 24, 2013)

In[2]:= f1=Piecewise[{{Piecewise[{{a1,StringMatchQ[x,"Yes"]}, {a2, StringMatchQ[x,"No"]}},0],

StringMatchQ[y,"Yes"]},{b,StringMatchQ[y,"No"]}}]

StringMatchQ::strse: String or list of strings expected at position 1 in StringMatchQ[y,Yes]. >>

StringMatchQ::strse: String or list of strings expected at position 1 in StringMatchQ[x,Yes]. >>

StringMatchQ::strse: String or list of strings expected at position 1 in StringMatchQ[x,No]. >>

General::stop: Further output of StringMatchQ::strse will be suppressed during this calculation. >>

Out[2]= \[Piecewise] \[Piecewise] a1 StringMatchQ[x,Yes]

a2 StringMatchQ[x,No] StringMatchQ[y,Yes]

0 True

b StringMatchQ[y,No]

0 True

In[3]:= f2= PiecewiseExpand[f1]

Out[3]= \[Piecewise] a1 StringMatchQ[y,Yes]&&StringMatchQ[x,Yes]

a2 StringMatchQ[y,Yes]&&StringMatchQ[x,No]

0 !StringMatchQ[y,No]||StringMatchQ[y,Yes]

b True

In[4]:= f2 /. {x->"No", y->"Yes"}

Out[4]= a2

The warning messages after In[2] can be prevented by evaluating

Off[StringMatchQ::strse]

beforehand.