HBS, when you travelled to the Eastern part of Ukraine and had difficulties with understanding, it could have happened because they did not speak pure Ukrainian. They either spoke Russian or "surzhyk" - a dialect they use there. Surzhyk is a mixture of Ukrainian and Russian when Russian words are pronounced as Ukrainian (a bit complicated stuff, you would need several examples about that).
On the other hand, Ukrainian spoken in the western part may contain Polish or Hungarian words.
That's why I believe people from any part of Ukraine could be good partners if they speak pure Ukrainian.