How to deactivate my plugin upon deactivation of NextGen

You’ve got to actually check is_plugin_active. I would use something more like this, shamelessly stolen and modified from here:

register_activation_hook( __FILE__, 'dependentplugin_activate' );

function dependentplugin_activate()
{
  require_once( ABSPATH . '/wp-admin/includes/plugin.php' );

  if ( is_plugin_active( 'nextgen-gallery/nggallery.php' ) )
  {
    require_once ( WP_PLUGIN_DIR . '/nextgen-gallery/nggallery.php' );
  }
  else
  {
     // deactivate dependent plugin
    deactivate_plugins( __FILE__);
    //   throw new Exception('Requires another plugin!');
   //  exit();
    exit ('Requires another plugin!');
   }
}

Edit: just realize you’re looking for deactivate, not activate. Still, maybe this will get your brain working in the right direction.