Phone memory shows as nearly full in PC, but is not
Try reflashing the Rom with full wipe again but don't restore anything with Titanium Backup.

similar problems usually happen when I used to restore data with Titanium Backup especially if the android upgrade from Rom to another is significant (e.g 4.1 to 4.2). 

please try this and tell what happens :)

Edit: added my comment to the answer.