"Did something go wrong with my results? Is it possible to have so many "matches" but no concrete connections?"
Yes, it is entirely possible. Many of the low and very low confidence matches could be statistical coincidences. Others may be so distant that neither you nor your match has the documentation. For you to get a match, both you and your relatives must have tested. Currently, Ancestry DNA is available only in the United States so unless other American descendants of your father's Ukrainian and Polish families tested you will not get any matches on those lines.
For comparison, I have about 6,000 "matches" from three companies. Of those, five have identifiable common ancestors, and five more have identifiable common locations. That is a rate of about 0.17%. People with Colonial American ancestry, however, get a much better return.
I have found autosomal DNA testing much more useful for confirming matches that I have already found through traditional genealogy than for finding new relatives.