System Locking Up

I have a server that is locking up pretty frequently for serveral months. I have about 4 dumb terminals running off this server and it appears that when the system is about to lock up it starts to run really slow on one of the terminals and then the rest follow suit until it just craps out. We then have to reboot the server and it will run fine for a few hours or days and sometimes even a week or two before the problem occurs again. This can happen as much as 9 times in one day! I have checked for bad blocks on the drive and have found none. I have even gone as far as replaceing the whole system (minus the hard drive) to try and eliminate any hardware issues. Sometimes I get an error when the system locks up saying "keyboard macros are full." I have never seen an error like this before and I am confused on what it means.
I would appreciate it if anyone can give me any suggestions. My knowledge of UNIX is pretty basic.

Where it the error coming from? It doesn't sound like it's coming from the operating system - it sounds more like it's an application or terminal emulator you're using to me...
When the server locks up, what is displayed on the system console?