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.