You should never deactivate or uninstall or even install any thing which is not part of your theme without explicit user consent. If a theme can not work without a plugin, its functionality should be shipped as part of the theme, or it just have to live with whatever bug that plugin has.
The best you can probably do is to have an admin notice about the incompatibility.