Mentalblog’s answer comes from the Ohr Somayach site:
[I]n Yemen, the Jews painted eggs in honor of Purim. They sent these eggs to friends as mishloach manot gifts and ate them at the festive Purim meal. The Jewish community in Yemen was isolated for centuries, and they can trace many of their customs back to the time of the First Temple, so it's clear that they didn't adopt this practice from any other culture. Rabbi Demari also noted that it's conceivable that egg-painting was a custom among European Jews, and that they stopped doing so when it was adopted by other religions.However, this doesn’t really answer the Lag B’Omer connection.
A little more digging shows that painting eggs was a European custom which predates Christianity, with pagan origins, and it somehow spread further afield as well. In Jewish terms, there is a tradition of European Jews painting eggs on Pesach, which I'm sure must be related to Easter:
[T]here were localities in Poland where it was customary for Jews to "go for a vikup" during Passover. The practice (the Yiddish expression is related to a Polish word meaning "ransom") involved paying a visit to relatives, and receiving from them colored eggs, especially ones that were tinted yellowish-red with the help of a special formula fashioned from onion skins.The significance of the eggs here is that they symbolise the circularity of life and death.
In some Hasidic circles, including the Karlin and Lubavitch sects, the distribution of painted eggs took place later in the season, on Lag Ba'omer.
A children's magazine published by Chabad-Lubavitch in 1945 described the thrill of a group of children as they prepared for the festivities. One of the children was especially excited because "Mommy promised to prepare some hard-boiled eggs for my Lag B'Omer lunch--colored." When asked about the reason for this practice, she explained that the eggs are an expression of mourning for the death of Rabbi Simeon ben Yohai* which occurred on that day. However, Rabbi Simeon was very happy when the time came to surrender his soul to the Creator, because he knew that everlasting happiness awaited him. And so, while the Lag B'Omer eggs are to remind us of his death, their purpose is not to make us feel sad on this day. Lag B'Omer is a children's festival, and children love color. And so it became customary to paint the shells of the eggs in various colors to make the children feel very happy on Lag B'Omer.
However, it is not only in Europe that Jews were drawn to coloured eggs. In Afghanistan, the eggs made their ritual appearance earlier in the season, and were associated with the Purim festivities. Throughout the month of Adar it was the custom there to roll the eggs, to see whose could keep going the longest without breaking. For each egg that did get crushed in the competition, the children would curse Haman. In Kurdistan, coloured eggs were included in the Mishloah manot that were distributed to children on Purim.
Another source sheds some more light on the Bar Yohai story:
"Bar Yohai and his son Eliezer lived for many years in Palestine. There he grew to be an old man and there he died. Now it was a strange thing, but all the years that Bar Yohai lived no one had seen a rainbow in the sky. The rain came and the sun shone, but no rainbow appeared. But on the day that Bar Yohai died, someone happened to look up, and there was a beautiful rainbow reaching across the sky. It was shaped like a bow, and all the colors of the world were in it. [Although a great and faithful sage had completed his life without fully experiencing a messianic era, the unattained is still achievable.] The minute Eliezer saw that rainbow, he remembered something that his father had told him long ago when they were hiding (from the Romans) in a cave; refusing to leave their home or the study of Torah. He told the people about it.Anyone ever painted eggs on Lag B’Omer or know anything more on this? Maybe this would be a nice way for Diaspora Jews to celebrate a holiday which, compared to Israel where the whole country gets set on fire, they largely ignore (other than going to see movies and getting married etc.).
"`One day,' my father said, `a rainbow will appear in the sky with colors brighter than this, brighter than any rainbow you have ever seen. It will be a sign that there will be no more wicked rulers. Each person will sit under a vine and fig-tree and no one will make another afraid. At this time, the Jews who love Palestine will come from many lands and stay here forever and ever.' All this, said Eliezer, my father told me when we were hiding in the cave."
Note: The colored eggs have all the colors of the rainbow; a sign of God's covenant with all humanity that Creation would outlive destruction.