[COLUG] changing console resolution on Linux server

[Brian]

Over the last several months we have replaced the KVM's in our server
room.  We now have one Linux server where the console (non-GUI) will
not display on the new video display.  We receive an error of
"resolution is too high".  When we connect a regular monitor to the
system, the console shows up just fine, although the text is small
enough that I could easily say that the resolution is perhaps
1280x1024.

If it were a GUI login screen, I would know how to go about reducing
the resolution.  But how do you change the resolution on a CLI screen?