The query is already using that index, according to EXPLAIN in the first post:
Code:
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE thread range forumid forumid 6 119685 Using where
It's just that the number of matching rows is too big.
I'm afraid nothing could be done from the vBulletin side of things. Maybe some MySQL server tweaking will help to speed up that query.