Not sure about your PNP/npn idea.
How about tpic6a595? These could drive 8 fans without extra transistors. Each of the chip's outputs can sink up to 350mA at up to 50V. You would need 16~20 chips, but you would not also need any driver transistors, so the circuit would be much simpler. If you daisy-chain them and use the Arduino's SPI pins, you could use the shiftPWM library if you need to control the can speeds.
But if your fans are the 4-pin variety, you can just use the far cheaper 74ls595.