Hi Steve:

I've done both countries (Poland and Ukraine) in the past with my Honda ST 1100.

There's absolutely nothing to worry about in Poland so far as getting fuel, accommodation, etc. is concerned. The country is full of lots of very new and modern brand-name gas stations, built using the same blueprints that were used in your home town in the UK. You can use your UK credit card to pay for the fuel, either at the pump or you can go inside and pay afterwords, whatever you want. If you get way out into the rural part of the country, there may be fewer fuel stations, but that's not a problem if you fill up before you leave a city.

It's easy to find places to stay in Poland - simple hotels, or B & Bs, or guest houses. Do pay attention to security for your moto. Just about every lodging facility will have a secure garage, you just have to ask. At a B & B or a guest house, you can always find a simple security solution - park in the back yard, or the farmer puts your bike in his barn then parks his tractor in front of it, etc. You don't have to live in fear, but at the same time, due diligence is needed. Your hosts will understand and appreciate this.

I didn't like Ukraine at all. You can buy gas without problems - again, fill up in the cities, because you might not find fuel easily if you get well off the beaten path. Overall, though, I thought that the roads in Ukraine were horrible (verging on hazardous to life), and I was not impressed with the quality of life (or lack thereof). My suggestion is that you visit Slovakia instead - a much nicer country.

I just got back from a trip through Russia, Ukraine, and Poland, and pretty strongly disagree with the quote above. I didn't have a chance to get on really small roads in Ukraine, but I was off the expressway and had no problem finding gas or with the roads (with one exception, described below). I was also very impressed with the towns I stayed in, although they some of the more touristy places (Yalta, Odessa, Lviv)--all of these very nice places. The road in along the coast in the Crimea is simply spectacularly beautiful. Much of Ukraine is pretty agricultural, and yeah, those parts could be pretty dull.

The roads were all fine EXCEPT at one point I took my eyes off the road while looking for the right highway (no signs of course) and ran right through several enormous, square edged potholes in the middle of the road. The bike shrugged it off but didn't like it a bit.

Being Ukrainian...yes, I do not live in Ukraine for 7 years, but all my buddies there and I visit often.

PanEuropean - I am sorry to hear you had bad experience, please accept my apologies on behalf of my country
Here is some tips
a) I can only guess you visited Ukraine in "grey years" after USSR desintegrated. That was bad time.
b) it is a big country, you need to really plan you route, getting "off beaten path" is no good for country bigger than France. I guess if you visit places like say Yellow Knife in Canada it will not be best impression too

Here is situation now.
Fuel is no problem. LOADS of fuel stations, loads of competition. Usually it is simple - better is station better is fuel.
National roads no problem, rural roads - what do you expect? Traffic of TIR trucks from Western Europe destroy those roads. Do not hesitate to ask people what road is best - for example entering Kiev from Zhitomir or Chernigyv direction is no problem, but some of roads "in" are mess. Again - TIRs to blame.
Where to stay? Usually in any village you can find place to stay if you have positive attitude towards finding it. Just start talking to people. Stay away from very friendly but drunk people - they may not be harmless, but their life and house and friends is a mess usually. Just like anywhere. Best is to find good old nice and accurate "babushka" and pay her a bit to have night in her house. Most probably she will feed you really well too. But if you go to any relatively major road you will see a LOADS of cheap and clean motels with place to stay, park and feed. And most often with security guard.
Speeding - no stationary cameras, mobile teams with radars, all "fixable" with some small fee But you have to follow their game, usually senior guy play bad cop and let you speak to lower rank, who takes money. Corruption? Yes, sad but it is true. But bikers often get off with just chat or souvenir.
Worst piece is car drivers. Bigger car = worse treat. If you spot somebody overtaking via opposite lane and no intend to notice you - just let him go, really. Those people are shame of my home country and no money will make them better. Some foreginers behave like that too - they think they have enough cash to buy off any policeman in case of accident. I know it first hand - accompanied some Europeans there
Border is simple, they were correct about Ukraine-Romania border, is no good.
Best places to visit - oh, do not get me started. Crimea - seaside (not central tourist places thou), but mountains is what you have to aim for there. Local "grand canyon", Dimerji, cave cities Mangup-cale and Chufut-cale, Vorontsov castle, Sevastopol (black sea navy city), loads. Visit Balaklava - famous place, very little. Winston Churchill stayed there once, it has nice ruins of byzante castle (visantian? vizantian? not sure what is right).
Black sea center - of course Odessa
West - Karpaty mountains, Lviv, castles, Hotin town, Kam'yanet's-Podilsky (strongly recommend).
Center - Kiev of course, 1500+ years old city, first capital of old Russia, Uman (nowadays jewish place of pilgrimage, but it has great places to visit).
East - forget it. Industrial, boring, but great bike following in Dnepropetrovsk. You can always get some contacts on website MotoTravel.info :: ÅÑËÈ ÒÛ ÍÅ Â ÄÎÐÎÃÅ, ÒÎ ÒÛ - ÍÀ ÎÁÎ×ÈÍÅ, my nickname there is same.
If you need any more info or contacts - just let me know.