Leave your desktop rez to what you had (that must have been ugly!). How high of a resolution does the game menu allow? I would try both the campaign and battle map at the highest.
If that doesn't work, set both the campaign and battle map resolutions to 800x600, and try to run in Windowed mode. To run in Windowed mode, you will need to change your game shortcut properties to something like this:
Code:
"D:\games\Total War\Medieval - Total War\Medieval_TW.exe" -strictserver D
Basically, you want to add the "D" to the end. If this works, be aware that the game is also running in the -ian mode, which allows you to change factions and do a lot of other debugging functionality.
Bookmarks