I had similar problems. Ukraine isnt easy even if you have a contact. My understanding is that the contact has to travel to the local police station and register your details, guaranteeing that you are staying with them.
I was able to contact a firm who specialize in Russian and The Baltic States' visa's , unfortunately I forget how I found that site. Im not sure whether it was in the visa section on the HUBB? or I just did a simple search. Either way I didnt go to alot of trouble to find the site and they were very efficient. I have a friend in Ukraine who would be able to assist you. Contact me if you need to.
Good luck
|