In most cases multiplayer will improve the framerate of your game. No longer runs complex A.I routines, instead, your entities receive updates from the server instead. Unless of course, your system for smoothing out server updates is insanely complex.

I wouldn't rag on locoweeds tutorial, he uses a different method that really isn't meant for FPS games. I've a full fledged multiplayer game(without the fancy lobbies and chat yet...) but 8 players, racing, and battle mode with 16 weapons 2 functions each enabled. This includes targeting, particles, ect. The reason for 8 players is due to my own limit(level design). I'd like to think that beyond this is possible. Remember, if your seeing really bad lag, emit some more "smoke" to hide it. Check your smoothing systems.

I cannot provide a demo to prove this right now, as I'm not going to share the code(much to complex/large to learn from anyways). However, it's really not that hard to do yourself(if you understand c-script, pointers, ect.), read through the years of "Multiplayer forums", and look for a western demo somewhere on the forums, and theres another begginers tut on AUM.