Accessibility MAJOR issues

I'll be honest, I'm having a hard time understanding the post. I assume you're listing steps that you've tried to take to end up where you are having these issues? Maybe a few questions could help clarify:

• Assuming that you have set up your InDesign file correctly for 508 compliance (there are a LOT of obsolete processes that exist online, so be careful there!), you then exported that document to PDF. Why use autotag at this point if the file correctly tagged the PDF on export?
• Assuming I'm reading the post right, you took one path and applied autotagging which created errors. You then took another path and used the PDF (as exported) direct from InDesign without autagging. Correct? 

Correctly tagged tables can be quite dense, in my experience! It is not a one-and-done tagging process. Yes, you can select some random element on your PDF page and just tag it as a table, but there are several internal tag structures that you have to have just so for the table to function correctly in a screen reader. For example,  <TR> for Table Rows; <TH> for table headings; and <TD> for table data cells. Each must be in a particular order and/or nested tag groups to not get an error. It's hard to know what your specific situation is with the description I'm reading.

To create a very simple model of a correct table tag structure, try opening a new Word document and inserting a basic 3-row, 3-column table. Put simple dummy data in the headings and body cells to track what is what in the tag tree. Save that simple table file as a PDF and review the resulting tag tree from within Acrobat Pro. That will provide you a basic road map for table hierarchy. Use that as a model to determine how your InDesign table should more or less break down.

It's not a 1-to-1, but it's a start. Issues could be from the design of the table itself. As a designer, I've seen so many well-illustrated and visually pleasing tables, but such designs do not always translate to a true table structure.

• A lot of times you can google the specific error for more context. I'll agree that Acrobat errors can be vague! Still, are you saying that the "Header Failed" errors are the only errors you are trying to resolve, but cannot find them?

Someone else may reply with better guiadance, but it would help to explain what it is that you want to do, specifically, as there are so many variables in a correct process as it is. Screenshots could help too, if that's possible?