TeX typesets paragraphs of text on to a (conceptually) infinite galley and then at certain times the Output Routine is invoked which splits off part of this galley and makes up a page, adding floats, the page head and foot, and footnotes etc. An important thing to note about this asynchronous nature of the page breaking is that the page breaker can not affect line breaking. All aspects of fitting the content to a horizontal measure have already been completed before the page breaker is invoked.
This means that it is virtually impossible in classic TeX to change the page layout (for example as here change between one and two columns) without having a forced page break.
If you force a page break you force a synchronisation point between the paragraph breaker adjusting the horizontal measure and the page breaker adjusting the vertical measure and things become a lot easier.
Unfortunately this means that you have to manually insert the command to switch to one column at the least disruptive place, add the table, then switch back. You can not rely on the latex float mechanism to find this for you.
This is essentially a limitation of the underlying engine rather than of LaTeX. You can find papers going back before TeX3 in the 1980's suggesting ways of extending TeX in this area.
See http://latex-community.org/know-how/latex/55-latex-general/475-e-tex for Frank's TUG article on how many of those old proposals for extending TeX are actually addressed by the current engines.