These are the skills actually that are needed to implement an RB tree (lot of special cases to handle, hard to organize the code well), although I have never been asked to implement any balanced tree on an interview.
If you haven't done that, it is a good indication of how you will handing boring but necessary and important stuff at work. In all fairness, I think you can't fault people wanting to judge you based on that..
It's not about learning algorithms. If you do the Stanford MOOC on algorithms on Coursera, which is one of the best MOOCs I've ever come across, you'll find that the instructor emphasizes understanding over rote learning and implementation details. If you understand what data structures and algorithms fit where, you can look them up and apply them as and when you need to. Memorizing every nook and cranny of CLRS so you can reproduce it quickly in an interview is a terrible waste of time, imho.
I wish more companies would hire based on code that you've written, than a bunch of contrived puzzles you're supposed to know by heart so you can solve it on a whiteboard without blinking. But, since that's how the fucking system works, I'm forced to spend time committing these things to memory than writing actual code.
James Hague said it best, "Organizational Skills beat Algorithmic Wizardry". http://prog21.dadgum.com/177.html