Bundling a plugin with a theme is indeed a-bad-idea, but note that this is different than a theme adding extra functional support for use with a specific plugin.

I'm working on a special-case theme at the moment, and I plan on providing additional functionality in it for use with a specific plugin that fits the use-case nicely. Using the plugin will be optional, but it will detect whether or not the plugin is installed and if not, suggest to the user to install it, for additional functionality.