Personally, I disagree. I always thought it was wasted space. If your icons are so confusing (or your users are so dumb) that you need a legend to explain that "this icon means new posts, this icon means no new posts," you should probably think about getting new icons (or users ;)). Because if your icons are well-designed, people aren't going to need someone to explain which one means what.
Just my $0.02.
---Jamin
