I played for a good while on the EV1-Alt servers (updated to build 18) and experienced no lag, however a couple people did complain about the lag, which leads me to believe it's client-side. If it were server-side, everybody would have experienced it, including me, but I had the netgraph up the whole time and it never spiked except for map loads. Some of the descriptions above make it sound like it's server-side, though, like when you freeze and move back and forth and the phonejack icon. Do these happen only on player connects?
I didn't realize Graffiti had updated or I would have tested there, too. I will try to do that tomorrow if it's still running build 18. I don't think I have the specific build that was up on graffiti before, but you should be able to run the gamei386.so file that came with build 16. The build 18 paintball2 executable isn't really going to change much, and I would keep that up as it fixes some bugs.
Spook: That behavior sounds really strange. What server was it on? I'm not sure what your screenshot is showing. You're getting over 300fps, so it doesn't look like framerate lag, and there's no netgraph to show any network lag.