First don't use SELECT a.*, select only the columns you need. You can try using JOINS rather than join in the WHERE-part. It might get get the query faster.
SELECT
a . * ,
c.category_name,
d.user_id,
d.username,
DATE_FORMAT(b.reply_date, '%H:%i<br/>%d/%m/%y') AS last_post_on,
b.reply_id,
e.username AS last_post_by
FROM tbl_forum_threads a,
LEFT JOIN tbl_forum_replies b ON a.thread_id = b.thread_id
LEFT JOIN tbl_forum_categories c ON a.thread_category_id = c.category_id
LEFT JOIN tbl_users d ON a.thread_author = d.user_id
LEFT JOIN tbl_users e ON b.reply_author = e.user_id
WHERE
b.reply_date IN (
SELECT
max( reply_date )
FROM
tbl_forum_replies
WHERE
thread_id = b.thread_id
)
ORDER BY
a.thread_stickied ASC ,
reply_date DESC
In some cases it is better that let go a little of the normalisation to speed up the query. You might as an example store the userid and username from the person that created the thread in the thread table, making it one less join. You might do the same for the last person that posted, and include the time as well, making both one join and one subquery unnessecary. The category name could be stored there as well. Note that I'm not in any way trying to say that you should not store all this information as you do now, but you might want to store it in the threads table as well. Also note that it might do the insert queries slower to handle it this way.
Another thing you might consider is to use LIMIT, otherwise you will end up with to much data returned.
