Its probably much too late for this, but I just had a very similar problem (titles of private posts missing/disappearing, presumably stripped out inadvertently by the Private Suite plugin). One other result on Google for a similar problem with the same plugin. Was only happening on private posts. WP 3.4.1, Private Suite v2.
I worked around it by going into my theme (a heavily modified child theme of 2011), going into content-single.php and altering line 13 from the_title to wp_title. The titles returned to my private posts immediately and the only downside is that a Β» symbol appears before every title globally now. I’m currently trying to eliminate that though.
To remove that symbol, add the following inside the parentheses of wp_title
“”,true
Just realised that this will only fix the problem in single post view, and the problem may still be present in cat view, yearly/monthly/daily archive, author view and whole-of-blog view. Unfortunately this is where my meagre knowledge runs out. I think you’ve just got to make sure each of your corresponding templates is using wp_title instead of the_title, and include the above parameters whenever wp_title is mentioned. Check the commented help inside the 2011 templates for further help.
Can one or both of you post a screenshot of your Private Suite settings?