Private messages problem In Drupal 6.22, after installing 'User Relationships', APK , Content Profile and some related social modules. Then upgrading the server (Ubuntu), ans saw that private messages stopped being received by the users. 

I have disabled UR, APK et al. and updated the database, but it had not fixed the problem. I even dropped the whole database and used a backup from a time prior to adding social modules. No curing effect. 

The server still sends out emails and I am pretty sure that privatemsg permissions are set correctly, so that users should be able to send/receive privatemsges. 

This might be clue: The users can receive privatemsg from debug (privatemsg test module), but not from other users. Not sure what does this imply. 

I have really ran out of ideas and appreciate your hints.
So u upgraded Ubuntu, anything else? Php, apache etc? First verify using VMware it is in fact Ubuntu upgrade only that is causing the issue. You say you redeployed an older version of the db.  I would be tempted to do a full deploy just to try to reproduce including Drupal code. It's an odd problem, my instinct says possibly a difference in php version could potentially cause this.