I believe themes are all about the aesthetic look and general layout; and, plugins are all about functionality. Of course the two are not mutually exclusive, they should work well together and when doing so create something greater than either by itself.

Adding functionality to a theme is all well and good, provided it is not done for the sake of doing it. If the premise of a theme requires the functionality of, for example, a menu plugin to accomplish its end goals then it is obvious to me that the functionality should be included. Do themes need to include Twitter, Facebook, or anything similar (again, as examples) I think not, there are plenty of very good plugins that manage these functions all too well.

Just like @Brian commented:
... depending on the theme, the intended audience (mass consumption? or single client project?) and also depending on the feature.