This turned out not to be a bug in Calibre at all but my misunderstading
Calibre does
not embed a TOC in the ebook itself. However, if you press the Menu button on the Reader and go to the main menu for the book, there is a "Table of Contents" option which will take you to the TOC created by Calibre. This is easier to use than an embedded TOC as it is easier to get to.