Just had an interview on a CS graduate from a top university with several years industrial experience who cannot even write pseudocode to rotate a binary tree. What is wrong with this world?

How many degrees you want it to rotate?

Could have drawn a tree and the rotated the whiteboard slightly.

But seriously, is this something that's actually done at the job?

Maybe they are in the binary-tree-rotating business?

All of you are not wrong, but at this level you should be able to improvise this algorithm, if you don't know it (and the exercise would be pointless if the guy knew the algorithm by heart).
It's not about rotating a binary tree, it's about evaluating the programming skills of the interviewee. That he actually manager to rotate the tree or not is not that important, what's important is to see how the guy think and react when confronted to something he doesn't master!