Found the problem. Private suite does its thing by hooking onto the save_post action, blindly sets the status to private for posts within the specified categories. wp_trash_post calls wp_insert_post which trips the save_post action, resulting in the posts status being changed back to private.
Here’s the patch (line numbers may be off a bit, since I have local fixes for other foibles too):
--- private-suite.php~ 2012-06-26 11:33:04.000000000 -0500
+++ private-suite.php 2013-07-17 08:43:53.000000000 -0500
@@ -83,7 +83,9 @@
if ($parent_id = wp_is_post_revision($postid))
$postid = $parent_id;
$options = get_option('private_suite');
- if (get_post_type($postid) != 'page' && in_category($options['categories'], $postid)) {
+ if( get_post_status($postid) != 'trash' &&
+ get_post_type($postid) != 'page' &&
+ in_category($options['categories'], $postid)) {
// unhook this function so it doesn't loop infinitely, update the post, then re-hook
remove_action('save_post', 'set_private_categories', 10, 1);
wp_update_post(array('ID' => $postid, 'post_status' => 'private'));