I think I fixed it temporarily by manually balancing the servers on certain CPU cores. I think there shouldn't be any lag now until the next update or the week day when I can reboot the machine without kicking a bunch of players.
The problem seems to occur after upgrading to Ubuntu 12.04 without rebooting. For some reason it is fine for many months, but suddenly the OS cannot properly load balance between multiple CPUs, ending up in 4 CPUs at 100% and 4 CPUs at 20%.