Keep in mind, as you research, that Eastern European borders were changing during these decades. Poland in particular. It was part of the Austrian Empire, then was taken by Russia, then by Germany. An American descendant answering census records, etc may not have been aware of the political division his parents or grandparents were from and may have responded with what currently used in the USA at the time the record was taken. Many census workers, city hall registrars, etc may not have been well-educated in European politcs/geography .
Records giving Ukraine as a place of birth may be referring to events in Bessarabia and Moldava and after the Crimean War, Wallachia