This is a tricky little issue. It turns out that \include differs from \input in an important way; it doesn't just add a couple of \clearpages. I think the right solution is to make a custom \include command which functions almost like the usual one:
\newcommand{\myinclude}[1]{\clearpage\input{#1}\clearpage}
When you use \addcontentsline, directly or indirectly, it writes a line on the aux file saying "write this and that to the toc file". Then it reads the aux file and follows that instruction. When you run latex again, the toc file has the right stuff in it and you get a nice table of contents.
But the tex \write command has some sort of delay to it (that I don't understand). When you use \addcontentsline several times in a row, it doesn't matter because they all go on the write stack in the right order. But here's the tricky part: when you use \include, it makes a separate aux file for the file you're including and immediately writes a command in the main aux file saying "go look at that other aux file for instructions" (with no weird delay). So if you use \include immediately after an \addcontentsline, the "go look at the other aux file" command gets written before the "write some stuff in the toc file" command. So all the contents entries from the included file get written first!
\addcontentslinewas not adding bookmark entries in the resulting PDF, unless there was additional text after the command. Bizarre. – jevon Oct 13 '11 at 02:07