Some suggestions:
Medieval Warfare - Sounds basic, but cards that feature cross bows, ballistas, maces and old medieval maneuvers and troops like insignias, flanking, charging and the like.
Winter - It's Christmas soon, think of a medieval/feudal setting in winter time, with lots of winter-based themes. Northern Lights, Fuel, Furnace, Hearth, Furrier, as well Blizzard, Maelstrom and Hibernation might all be card names.
Medieval Court/Titles - Still all kinds of medieval court, titles and names to use: Thanes, Criers, Earls. Chequer, Cardinal, Arch-Bishop, Parliament, Abbey, Puritan, Yeoman, Exchequer, Roundhead, Royalist
Civil War - Feudal times were ripe with civil wars (check out England's history with them some time), this means rebellion, treason, banishment and sects within your own deck actively working against you and ways for you to put cards in your opponent's deck that actively work against his.
These are just random ideas off the top of my head, but maybe they help lead you to the place you need to go to get started!