I just struck the same problem. Here's what I found:
If you use the Atto HTML editor, its "(large)", "(medium)" and "(small)" headings translate to <h3>, <h4> and <h5> respectively. However, the Table of Contents generation expects the heading levels to be <h1>, <h2> and <h3>. Manually editing the HTML and correcting the heading levels gives correct ToC generation.
The TinyMCE editor doesn't have this problem - its heading levels map to the correct HTML.
However, if you're using the "Clean" theme, you'll now find that the wiki name at the top of the page is now formatted as <h2> and the page title is <h3>. But inside the page, your section headings will now be a much larger <h1>.
I'm guessing there are two ways to fix the problem, and both involve a lot more digging into the guts of either the theme CSS or the wiki PHP code:
1) Edit the CSS so that the wiki title (which is in a <div role="main">) and the page title (which is an <h3> with a unique ID, e.g. <h3 id="yui_3_17_2_2_1439114035470_605">) are given a larger or more distinct font and the top-level heading in the page (e.g. <h1 id="yui_3_17_2_2_1439114035470_620"><a name="toc-1"></a>Top Level Section <a href="edit.php?pageid=24&section=Identity+Management+Principles" class="wiki_edit_section"></a></h1>) is a smaller font.
2) Change the wiki code so that it processes <h3> - <h5> as levels 1 - 3.
It might be interesting - I don't have time tonight - to edit the HTML directly so that the top-level heading is <h3 id="xxx"><a name="toc-1"></a>Top Level Section . . . </h3>. I wonder if that would parse as a level 1 heading while remaining an <h3> in terms of format?