D5 to D6 upgrade causes really long queries causing page loads excess of 3 minutes for /forum page

I just recently upgrade my D5 community site to D6 (test setup). The /forum page loads times have increased dramatically (from 5 sec page load to +3 min). The problem only occurs for the main "/forum" page, inside pages load fine. From my research and chatting with fellow Drupalers I think there could be a few reasons why this is occurring.

One reason which people have pointed out is possibly due to n.type = 'forum' condition having been removed from the forum_get_forums() function. I introduced this condition again into the queries and the load time got reduced from 3 minutes for the /forum page to roughly about 25 seconds.

Now if I run the below query (from the function forum_get_forums()) on my D5 installation it would take .2 seconds, but if I run the same query on my fresh D6 upgraded db, it would take about 8 seconds. See below the explain when run for the D5 and D6 databases:

Output from explain run on my D5 database:

mysql> explain SELECT ncs.last_comment_timestamp, IF (ncs.last_comment_uid != 0, u2.name, ncs.last_comment_name) AS last_comment_name, ncs.last_comment_uid FROM node n INNER JOIN users u1 ON n.uid = u1.uid INNER JOIN term_node tn ON n.nid = tn.nid INNER JOIN node_comment_statistics ncs ON n.nid = ncs.nid INNER JOIN users u2 ON ncs.last_comment_uid=u2.uid WHERE n.status = 1 AND n.type = 'forum' AND tn.tid = 64 ORDER BY ncs.last_comment_timestamp DESC LIMIT 0, 1;
+----+-------------+-------+--------+---------------------------------------------------+---------+---------+-------------------------+------+----------------------------------------------+
| id | select_type | table | type   | possible_keys                                     | key     | key_len | ref                     | rows | Extra                                        |
+----+-------------+-------+--------+---------------------------------------------------+---------+---------+-------------------------+------+----------------------------------------------+
|  1 | SIMPLE      | tn    | ref    | PRIMARY,nid,tid                                   | tid     | 4       | const                   |  221 | Using index; Using temporary; Using filesort | 
|  1 | SIMPLE      | n     | ref    | PRIMARY,node_type,status,uid,node_status_type,nid | PRIMARY | 4       | ql.tn.nid               |    1 | Using where                                  | 
|  1 | SIMPLE      | u1    | eq_ref | PRIMARY                                           | PRIMARY | 4       | ql.n.uid                |    1 | Using where; Using index                     | 
|  1 | SIMPLE      | ncs   | eq_ref | PRIMARY                                           | PRIMARY | 4       | ql.tn.nid               |    1 |                                              | 
|  1 | SIMPLE      | u2    | eq_ref | PRIMARY                                           | PRIMARY | 4       | ql.ncs.last_comment_uid |    1 | Using where                                  | 
+----+-------------+-------+--------+---------------------------------------------------+---------+---------+-------------------------+------+----------------------------------------------+

Output from explain run on my D6 database:

mysql> explain SELECT ncs.last_comment_timestamp, IF (ncs.last_comment_uid != 0, u2.name, ncs.last_comment_name) AS last_comment_name, ncs.last_comment_uid FROM node n INNER JOIN users u1 ON n.uid = u1.uid INNER JOIN term_node tn ON n.vid = tn.vid INNER JOIN node_comment_statistics ncs ON n.nid = ncs.nid INNER JOIN users u2 ON ncs.last_comment_uid=u2.uid WHERE n.status = 1 AND n.type = 'forum' AND tn.tid = 64 ORDER BY ncs.last_comment_timestamp DESC LIMIT 0, 1;
+----+-------------+-------+--------+------------------------------------------------+-----------+---------+-------------------------------+-------+----------------------------------------------+
| id | select_type | table | type   | possible_keys                                  | key       | key_len | ref                           | rows  | Extra                                        |
+----+-------------+-------+--------+------------------------------------------------+-----------+---------+-------------------------------+-------+----------------------------------------------+
|  1 | SIMPLE      | n     | ref    | PRIMARY,vid,node_type,uid,node_status_type,nid | node_type | 14      | const                         | 41256 | Using where; Using temporary; Using filesort | 
|  1 | SIMPLE      | u1    | eq_ref | PRIMARY                                        | PRIMARY   | 4       | qltestd5.n.uid                |     1 | Using where; Using index                     | 
|  1 | SIMPLE      | ncs   | eq_ref | PRIMARY                                        | PRIMARY   | 4       | qltestd5.n.nid                |     1 |                                              | 
|  1 | SIMPLE      | u2    | eq_ref | PRIMARY                                        | PRIMARY   | 4       | qltestd5.ncs.last_comment_uid |     1 | Using where                                  | 
|  1 | SIMPLE      | tn    | ref    | vid                                            | vid       | 4       | qltestd5.n.vid                |     1 | Using where                                  | 
+----+-------------+-------+--------+------------------------------------------------+-----------+---------+-------------------------------+-------+----------------------------------------------+

Notice the first row in each of those explains for D5 shows the value 221 rows as apposed to for D6 shows rows values as 41,256.

Anybody has any input as to why such a huge discrepancy in these numbers and why the same query on D6 take so much longer compared to D5.

Note: There is one difference between the 2 queries, the field vid is used in D6 for the table term_node whereas nid is used in D5. I don't have revisions enabled for the most part on my site so I figured this wouldn't make such a difference (perhaps I'm wrong).