Use two TLC5940, and only use half the OUT pins by only connecting 8 LED arrays to each TLC5940. Connect the TLC5940's in series, and so there is no extra pins needed to drive the TLC5940s.
Then for the power calculations, the power dissipation is halved.
That datasheet for the LEDs says the worst case (lowest) voltage drop is 3V.
So, 3 LEDs is a series 'string' 3x3V = 9v
Resistor voltage drop = 12V-9V = 3V
current = 3V/150Ω = 0.02A (20mA)
Three parallel set of three series strings = 0.06A (60mA)
16 sets of 0.06A strings is 0.96A (960mA)
Looking at the graphs in the TLC5940 datasheet, its voltage drop for a 60mA current could be under 1V (Figure 5 and 6), which will reduce the current, but yields a worst case power dissipation of:
0.96A x <1V = < 0.96W (about 1W)
The PDIP package's thermal impedance of 48°C/W, so 1W raises its temperature by 48C.
The maximum operating temperature is 85C, so that might be a bit tight if the electronics are inside a box, but maybe okay if it is exposed to the air, operated it in an office (e.g. with air conditioning).
The other packages have better thermal characteristics, so you could design a PCB, and use them. However, if this is for a small number of systems, it might be as easy to use two PDIP TLC5940s and get more headroom.
EDIT:
Remember, the total light output from an LED will be reduced if it is being multiplexed because it is only on for a fraction of the time. So multiplexing may not be a useful option. If it is a useful option, because the LEDs do not need to be fully powered all of the time, then the TLC5940 could probably drive the LEDs directly, running at a lower PWM cycle than full-on, and hence needing to dissipate less heat, anyway.
The thing that destroys semiconductor electronics is temperature, not just power.
So even if the spec says the TLC5940 will handle the power, it might still malfunction if it gets too hot. If it were enclosed in a box, the ambient temperature would rise, and even though the TLC5940 PDIP can dissipate 1W for a 48C temperature rise, inside a box heated to 40C, and it is operating beyond the recommended spec.
If the TLC5940 runs above its recommended 85C maximum, it will fail much more quickly. A high enough temperature might even damage it (I have used older parts with 'thermal protection' but they have still been destroyed by overheating). Even if the chip's thermal protection works, the effect may be to reduce the brightness of the lights, so trying to run it too hot may be self defeating.
So, as long as it is cooled enough, then even the PDIP TLC5940 (its worst package for thermal dissipation) should be able to handle 1W without the temperature rise reaching 85C.
Personally, I would try to do some experiments to get some actual data. The calculations indicate it should work fine, but actual conditions are a real factor to consider. Superb heat sinks but an ambient of 40C might still affect the life of the part.
You could easily limit the current below this level, if the light output is adequate, and hence reduce the heat generated, lowering the temperature of the part. The TLC5940 makes this straightforward; adjust the single 'programming' resistor on the TLC5940. So it should be a safe and straightforward experiment to do. Start with a lower current, say 2/3rds what you think you need, and have a look at the results.
If a lot of light is critical, I would seriously consider offloading 20%+ of any TLC5940's load to an extra TLC5940 to give me some temperature headroom. That alone might be enough, and avoid any of the the extra complexity of trying to multiplex, or use external transistors.
END EDIT
Best Answer
The problem you have is one that is a design problem. You need to realize that the three LEDs in one string may very well have a higher total voltage drop than the three LEDs in the parallel string. The ones with the lower voltage drop may light while the others do not.
Since you do not have any intentional current limiting scheme to control the current flow through the LEDs in your testing scenario you are depending upon the forward voltage drops across the LEDs to be more than the sourcing power supply. In this scenario the effective internal resistance of the LEDs and the resistance of the wiring harness are being used to limit the current. Operating in this mode the V / I characteristics of the LEDs can shift with time, aging of the LEDs and the current operating temperature of the diode junctions within each LED.
The solution is to provide for a separate driver for each string of three LEDs or to place a resistor in series with each of the three LEDs that are already in series.