Here are a few things that I would check. I have a feeling #1 might be your problem.
1. The <title> tag in the pligg.tpl file should look like:
2. in your database, look in your links table to see if the title is being stored
3. for kicks, edit story.php and hardcode in a title by changing this:
Be sure to delete all the cache files in the templates_c/ cache folder, and reload the story page. If the page title says "this is a test title" then no problem there.
$main_smarty->assign('posttitle','this is a test title');
4. Did you add <title> tags to any of your files that would override the real titles? Not sure exactly how you could override it, but I'm sure theres a way.