This will happen if the text is stored in the DB as HTML Entities (something like া instead of the actual symbol).
Can you check your thread title column in phpMyAdmin and see how they're stored there? For the record, here's a screenshot of phpMyAdmin's thread title column when UTF-8 titles will NOT work: https://www.dropbox.com/s/fw1pu7uppd3srxz/Screenshot 2013-12-26 13.12.43.png - if it looks like this, your screenshot is correct.
They might, but please do bear in mind that you need to test this thoroughly on a backup site. You should not attempt to do this on your live site until you're 100% sure it will not break any of your legacy content.
There is no solution other than to convert your database (and potentially break legacy content) as described in post 6 to 8 on the previous page of this thread.