Can anyone explain? Is there some rule for when to use на and when to use в?
It's because the word "Ukraine" becomes from Russian "Украина" which means "у края" (the source word is "край" (eng. edge)) or "окраина" (eng.: "closed to border"). And in Russian language it is correct to say "я живу на окраине" and the same way for "я живу на Украине".
But nowadays Ukrainian government prefers to forget that Ukraine was a part of Russia and they say that "Ukraine" has another mistyficated root.
So officialy, in Russia it is correct to say "на Украине", but it is also okay if you say "в Украине". But in Ukraine you have to say only "в Украине" for political reasons.
As others have pointed out, this has become politically loaded, I would say since the breakup of the USSR and Ukraine becoming an independent country. Here is a detailed and more or less unbiased analysis of the controversy:
To summarize, both prepositions are technically correct, "на" being much more common at least in the 20th century and supported by the "окраина" etymology, "в" emphasizing a separate country and usually implying an alternative (very contrived) etymology. The definite article was dropped in English also for that reason (compare to The Netherlands).
"В Украине" sounds jarring to my ear, but it is technically not wrong, there are examples of this usage from 19th century Russian classics. From that point of view it just sounds like an anachronism today. Ironically, possibly the most famous poem by the most fervently patriotic 19t-century Ukrainian poet Taras Shevchenko uses "на".
To answer your question, use "в Украине" if you want to please Ukrainian patriots/nationalists or want to make a political statement, use "на Украине" if you want please the purists, or avoid the construct altogether if you want to be neutral.
В Украине is the variant used in the Ukraine, including its Russian-speaking parts, and is considered the normative there since early 1990s. Approximately at the same time, the country lost "the" article in its official English name and become just Ukraine.
In Russia, the usage with «в» has long been considered a dialectism among others, but later it received a political meaning. It became even more confusing in the recent crisis, when «в Украине» started to be identified with pro-Russian activists in the East, not only with Ukrainian nationalists. Currently one can hear both usages on both sides of political spectrum, but «на Украине» is still considered academically correct.
Interestingly (or not), I think there's a similarly politically loaded issue when referring to the country in English: does one say "He is from THE Ukraine", or "He is from Ukraine"? The use of the definite article ("the") suggests that the speaker is thinking of a region rather than a sovereign state, and for that reason, I think that the use of "the" has been disfavored (perhaps officially) since 1991. Still, dropping the article sounds unnatural to me -- though perhaps that's probably because I grew up during the Cold War.
Does not have anything to do with окраина. Does not have anything to do with "politics". If "окраина"="Украина", then it is the same as Ямайка, Гаити, Байкал, Дальний Восток, Сахалин, Кавказ.
As you can see many geographical places have absolutely no relation with "окраина".
Relative use of preposition for countries is a part of every country. This could be only learned by memory. But there is some useful tricks. Islands and peninsulas are typically "на".
На Ямайке, на Гуадалканал, на побережье и т.д. При этом "в Англии", "в Казахстане". Но при этом "на Каракумы", "на Ладожском озере" и т.д.
But if you suppose that all islands and closed/non-central regions are used with "на" - you are wrong. Examples: в Японии, в Исландии, в Гренландии, в Голландии.
As you can see, relative choice between в/на does not relates nor to size, nor continuity, nor closedness of object, nor relative placement. Equivalence of "окраина" and "Украина" is used by idiots.
I think there is no actual difference. Also there are no language rules stating that.
Before USSR decay if was most often said "на Украине". Nowadays some Ukrainians wish we say "в Украине" to respect their independence.
So, this is political question. If you wish to respect Ukrainian independence you can say "в". If you wish to respect denial of Ukrainian independence, you can say "на". If you are in politically neutral topic, you can say "на" as it was common many years.