Losing my wallet put me off a bit and I am worried about going to Ukraine now. I had not even left the EU before something like that happened. The absolutely worst case scenario would be ending up without passport or a penny somewhere in the middle of Ukraine.

TRANSDNIESTR REPUBLIC
It turns out that there is a "country" between Moldova and Ukraine, that is not on the map because it is not officially recognize.
But it has its own borders, currency etc.
...
Does anyone know anything about this - is it a place to visit, or avoid?
I, personally, would be more suspicious to Moldova and the "Transdnestr Republic" in the point of safety. Some my friends frequently visited Ukraine last years and had not meet any problems whatsoever. I believe that the place you are staying now (Moldova and the Transdniestr republic) is the most dangerous places in that region.

As for pickpocketing, It can happen everywhere, just be careful.