To calculate the maximum power dissipation in the transistor, you need to assume the minimum voltage drop in the LED (3.2v for the green and blue) and across the current sense resistor (say 0.6v). This gives 1.2v (assuming a 5v supply), which at 350mA gives a dissipation of 420mW. To this, you need to add the dissipation due to base current, but that should be only 20mW or so.
Vce(sat) for that part is quoted at 500mA collector current and 50mA base drive. You can't provide 50mA base drive because your TLC5940s would get too hot. You'll need to run with something like 10mA base drive instead. Looking at that data sheet, the transistor looks like it may not have sufficient hfe at 350mA to guarantee a low enough saturation voltage. Also note that the power dissipation limit assumes 6 sq cm of copper as a heatsink, per transistor.
No, it's not that bad to use just a series resistor, especially as your new LEDs now give you 1.4v minimum voltage drop across the resistor. [The higher the voltage drop across the resistor, the better the current regulation, at the expense of more power dissipation in the resistor.]
If you use the resistor, you might wish to consider using mosfets (e.g.
http://export.farnell.com/toshiba/ssm3j02t-te85l-f/mosfet-p-ch-1-5a-30v-sot23/dp/1714372 or
http://www.farnell.com/datasheets/25641.pdf) for switching the leds, because this keeps the dissipation in the TLC5940 low, at the cost of needing a resistor (say 1K) to pull the mosfet gate high when the TLC5940 output turns off. Make sure the series resistors are adequately rated, e.g. the one for the red LED will dissipate up to 1W in this configuration.
Yet another possibility is to use a constant current driver in which the transistor passing the current is replaced by a mosfet - thereby avoiding problems of saturation voltage and allowing the TLC5940s to be run at a low current so as to keep them cool. This may be the best solution.
The other thing you might want to consider is whether it is still worth using TLC5940s, given that they are not cheap and you are unable to get the benefit of the constant current output.