Choosing appropriate names can really add an extra layer of believability to your mission. Choosing names that sound too modern (eg, "Dave") or too fantasy-like, ("El'drith Blackstone") can spoil an otherwise excellent story.
In the TDM setting, the original language of the Empire was Latin, so many religious and noble families have Latin-sounding names. Commoners generally have British names. Old families with ties to the lands conquered by the Empire tend to have Germanic or Gaelic-sounding names.
Here are some basic suggestions for picking character names:
Especially lowlifes and thieves: 19th century British names (think Dickens); usually short and undistinguished (e.g. "John", "Binnes", "Sykes", "Dogsley", "Meg", "Molly", "Snagsby", etc ). Adding a simple adjective in front is also effective (e.g. "Old Tom", "Pink-eye Cobb", "Mad Mary").
Norman nobility, occasionally Latin (e.g. "Quintus", "Beaurigard", "Eventroit", "Alraune").
Common British names, but often with slight changes or Germanic influence to suggest descent from old money (e.g. "Iacobus Willen", "Messer Johannes", "Robert Chapman").
Builders and those from the Capitol of the Empire
Common Italian, Latin or latinised ("Marcel" ["Marcellus"], "Casagave", "Guillave", "Tellis", "Ignatius").
Magi and Southerners
Near Eastern and Persian, a suggestion of exoticism ("Scarmengades").
Old Families or Pagans
Either Gaelic or Germanic names (e.g. "Carrigan", "Morgan", "Taggart", "Alric", "Tibold").
The following are some sites that could help you with choosing convincing given names and/or surnames for characters.
Choosing Place Names - Article with advice on choosing fictional placenames appropriate to the nature and tone of TDM's setting.
Historical resources - Article listing resources on real history, pertaining to various aspects of mundane life in a setting like that of TDM's. Feel free to use it for research and inspiration.