I will say that the Russian symbols on the title screen look great but could use a little work.
That would be a hammer and sickle. If I remember correctly the hammer represents industrial workers and the sickle represents farmers. I think it looks pretty good but some of the lines could be cleaned up a little, yes. Other than that I think it looks as good as NES graphics can be expected to look.
Thanks for the tips. My aim is to capture the Russian communism and their history as much as possible. I gave no thought to the kings at all. I would love to hear more from you if you've got any fucks to give.
Ah. The good old Soviet Union. Heh Yeah, Comrade Mario wouldn't want to help the kings he would want them executed for enslaving the masses. (or more accurately, to use as a scapegoat) LOL
EDIT: Perhaps the transformed kings (like the dog for example) could be repalced with the normal king graphics and instead of turning them back to normal you goal is to rescue your political prisoner friends who will then be usurping their thrones upon your successful completion of the boss battle. haha The dialogue upon entering the castles/palaces could be changed to reflect Mario confronting these monarches. He's there to help overthrow their governments.
Since you're going with the Russian side of things I can think of a number of interesting characters you may want to include or maybe look up for inspiration:
Joseph Stalin: One of the most notorious leaders of the USSR. This guy was one paranoid mother fucker and murdered more people than Hitler could ever dream of. On the plus side, in just a few short years he transformed Russian from an ass-backwards country of poor farmers that was probably 100 years behind (they lost a war to Japan, compare the sizes of the two countries and let that sink in) to one of the leading industrial nations of the 20th century. I always remember a famous quote of his "One death is a tragedy. A million deaths is a statistic."
Vladimir Lenin: The first leader of the Soviet Union, some believe he was poisoned by Stalin.
Leon Trotsky: One of Stalin's rivals. Probably would have been a much better leader. Many believe that Stalin had him assassinated.
I could list more USSR alumni but I decided to keep it old school.

These three are some of the most important individuals I can think of from the early days.
Non-Soviet persons of interest:
Karl Marx and Friedrich Engels: Widely considered the fathers of communism due to having written The Communist Manifesto in 1848. Both were German.
Mao Zedong (Tse-tung): First leader of the Chinese communist party. Was in power I believe from 1949 to maybe around 1975. This guy was probably just as crazy as Stalin if not moreso. He is probably responsible for more deaths than anyone in human history (though you will never convince a Chinese citizen of this historical fact, they're brainwashed into seeing him as some sort of saint, he's like the Chinese Jesus).
Pol Pot: This lunatic took over Cambodia in the 1970's. His army, the Khmer Rouge ("red cambodians"), dressed in black and were notorious for torturing people to death (and for very little reason). He had all sorts of crazy ideas. Basically, everyone was removed from their homes, sent to work on farms all across the country and nearly all technology in the country was destroyed (except for guns of course). No TVs, radios, cameras, watches, etc. It's almost like his idea was to send the country back in time. Strange guy.
Random ideas:
-Since Mario is a commie a good replacement for Bowser might be Uncle Sam. He symbolizes America and therefore capitalism and democracy. I've seen him used in a number of Chinese and Soviet propaganda pieces. The Russian royal family that was ousted and executed by the commies would also be a good enemy but Uncle Sam is very recognizable, whereas no one knows who Czar (Tsar) Nicholas II was except for history buffs.
-lots of old Soviet propaganda posters were done in a style known as "constructivism" and are quite striking, perhaps something could be done with this style
-lots of commies stuff has a red and yellow color scheme
-in a communist society men and women are supposed to be 100% equal, no bones about it. Perhaps the Princess could be turned into a revolutionary ally rather than just the standard "damsel in distress"
I don't know if this can be used in any way, but considering what usually happens when it is put into practice, I've always found it very ironic that the purpose of communism is to remove systems that stack the odds against the common person (in favor of the wealthy "elite") and give everyone their fair shot. It's supposed to be a good thing, yet for some reason it has almost always been used as an excuse for madmen to corrupt their government far beyond the so called "evils" that they are replacing for the purpose of dictating every aspect of citizen's lives with very little if no regard to the actual quality of said lives. This is all done under the guise of "for your own good". Communism is one of those things that makes everything sound perfect on paper, but in real life we are not robots and therefore these systems are always doomed fail. Though I suppose technically, there has never been a
true communist country. The dictatorial phase is supposed to be just that, a phase. If I remember correctly, in theory, after the revolution a country is supposed to go through a socialist phase until the communist system is established and there is no longer a need for government. This has yet to happen and all we've gotten so far are dictators using "communism" as a means to live like kings while their people starve.
Well, I guess that's all I got for now. I feel like I've been typing for a while. Hope this is helpful in any way.