Table of Contents with WikiMarkup no longer works after upgrade to 4.1

Problem:

Since we updated our Confluence to 4.1.5 from 3.5, we're facing broken links on Table of Contents. Every content that was linked, now is broken.

Steps to reproduce:

In a Confluence 3.5 or 3.4:

1. Add a page, write some examples.
2. Go to Table of Contents, and click on "Insert".
3. Done, now you have a table of contents.
4. Add this WikiMarkup, for example:

   {div:class=table_of_contents}
   {center}{span:class=toc_header}Contents{span}{center}
   {toc:style=none|indent=55px|maxLevel=5}{div} 
   

5. Migrate to Confluence 4.1.5
6. Access that page that you create before.
7. You're going to see, that all the Table of Contents links, will be broken.

note I've elevated this to a higher priority due that this breaks Confluence usage for upgraded Customers.