That looks a lot like a video card driver issue, and 10.9.1 seems to have added some new problems in video drivers.
This is most likely specific to your video card/GPU model (which would be good to know so we can try to reproduce it) - and you should let Apple know so they can investigate on their end.
Now I'm not sure if I should take the step and purchase the Photoshop Photography Program.....
I have an appointment with Apple today to see what the issue is, maybe they'll do a video card replacement since they have been having problems with this card.
The problem appears to be on both Windows and Mac, in various versions of the product. I've logged a bug and hopefully we'll have a solution soon. Thanks for letting us know about this problem and sorry for any inconvenience it might cause you.
There is still some random component involved, because I can't reproduce it all the time. (which explains why my first attempts worked just fine - bugs never show themselves when the developer is around 🙂
Followup: we reproduced it, and it wasn't a video problem. Unfortunately the bugs have been there a long time, and the fix is a bit complex - so it won't qualify to go in a dot release. But we have a fix for the next major release of Photoshop.