Mail.app on 10.8: How to get back the "N Messages Selected" label?
I usually just drag the selected messages a few pixels and then let them drop back. While you're dragging them, the number of messages is shown next to the cursor.

Not exactly the same thing, but it does the job for me.