|Takeru sword of susanoh has this scenario but they aren't your average medieval queens, they're queens of a country of amazon women.
There's a scene like that in Historie, though it is only about half a chapters worth
Spoiler (mouse over to view)
and the guy is commoner/soldier
If your ok with princess x commoner then Shuna no tabi has traces of this. (I say traces because their relationship is more a cross between romance and friendship and the princess is a slave, so no majestic palace settings and the such.)
There's also Good witch of the west for princess/commoner. This has the standard european style palace setting for part of it. The story is quite fairy tale- esque with lots of twists.