CS4 — ouch! Did you read my post CS4: The dreaded index …? That was on a just slightly larger document (and, from the complaints I have read on Adobe's Indesign Forum, I think index troubles are not even related to document size).
To get my index up and running, I had to write lots of custom scripts, so at least I now know how to gather all entries into a file, for example.
The tour de farce (so to speak) I mention at the end — a fully custom script that gathers index entries and their page numbers by itself, sorted & all — worked for me and my index; but that was only an easy one, relatively speaking, consisting only of single-level entries. It won't work for you without some serious re-writing, I'm afraid.
(I also don't feel like picking up the slack where Adobe fails to get it right! It's their job, and they ought to do something about it, what with us being paying clients suffering under some serious bugs that virtually makes the index function useless.)
(I'm fuming — sorry, I know.)