When gamers talk about "medieval" or "feudal" Japan, they're usually referring to the Sengoku or "Warring States" period of the mid-fifteenth through the beginning of the seventeenth centuries. This was a period of decentralization and destabilization, as power shifted away from the shogunate to local daimyos, bringing with it lots of military conflict and political intrigue. This makes it well nigh perfect for the kinds of mayhem characters in RPGs create, which probably explains the appeal of the era -- well, that and the ninjas.
The difficulty with Sengoku era Japan is that it takes place not only in the past but also in a foreign country. Most gamers haven't the foggiest notion about Japanese culture beyond what's been popularized (typically inaccurately) through comics, movies, and TV shows. To create a RPG set in the era that hits all the right notes is thus a difficult task. Many gamers want their historical games to be "authentic," but don't necessarily want them to be "realistic." That is, they're not content with games that get socio-cultural details wrong, even as they're not so keen for those details to get in the way of creating the cool character of their dreams.
It's a tough line to walk and, in my experience, very few RPGs of this sort ever succeed completely. One of the rare exceptions is 1981's Bushido. Published by Fantasy Games Unlimited and written Paul Hume and Bob Charette (who'd go on to lasting fame with their game Shadowrun), Bushido opted for a what might be better called a "mythic" approach to the Sengoku period. That is, the game's setting, Nippon, is historical Japan -- the place names and geography are the same -- but it's not strictly historical, since it's filled with ahistorical NPCs, events, and, in some cases, supernatural beings. It's a bit like the Ars Magica approach to medieval Europe, albeit subtler, since Nippon is much more "realistic" overall than AM's Mythic Europe. Consequently, Nippon somehow doesn't come across as nearly as intimidating as it might if it were presented simply as historical Japan, thereby making it a far better RPG setting in the process.
As a game, Bushido is very interesting. Its rules are complex, although not as complex as one might expect from an FGU product. Much detail is given to combat, which is both expected for an RPG of the era and for one set in medieval Japan. Of course, Bushido has rules for far more than combat, including skills, ki powers, and magic. As one would expect, the game also treats questions such as honor and status within Nipponese society, as well as how one acquires and loses them. It's here, I think, that Bushido really shines, at least if my experiences with the game are any indication. Players quickly acclimate themselves to the rhythms and values of Nipponese life once they see that many of the usual RPG problem-solving tactics will get them killed or, worse, ostracized. There's something truly glorious in observing this transformation in one's players and it's a testament to good game design that such a transformation is even possible, let alone likely.
I have a lot of fond memories of Bushido, which always struck me as more "serious" than any of its competitors, including TSR's late entry Oriental Adventures. I often call Bushido the "Japanese Pendragon" and I think it's apt: both games treat their subject matter with respect, adopting an approach that's neither too historical nor too fantastical, a middle road that encourages good roleplaying in a culture whose values are often at odds with those of contemporary Western society. That's an impressive achievement in any era. That it was achieved more than 25 years ago is all the more remarkable.
Plus, you've got to love any game whose random encounter table includes almost as many different types of "rude peasants" as the Dungeon Masters Guide does harlots.