This is a known issue that started with SP3. It will be addressed with 10.1.
Here are two related incident numbers in case you are interested in tracking:
NIM074169: "Rotate marker symbols with data frame" box in ArcMap Advanced Settings does not work in SP3. The marker symbols always rotate even when not selected.
NIM075697: Labels with 'US Route HWY' and 'US Interstreet HWY' turns upside down with the Data Frame Rotation applied
Jeff