It all depends on what the clients are running... Do you have any TSRs such as AV agents, or such... and are the clients using Lotus Notes? (Lotus is notorius for causing systems to crash because it uses too much resources on the machine). Or are the clients using any other apps such as CAD or graphic intensive apps that they keep open all the time?
I would say you are spot on about processing power. You might also try increasing memory.
What OS's do the clients have (I assume W2K).
Plus, make sure all BIOSs are up to date and the latest chipset drivers, etc.
Will