Grumpy_Mike:
That is odd for two reasons.
First of all the TLC takes in values from 0 to 4095 if you are only sending values from 0 to 255 you are missing a lot of values. Remember they are inverted so that the smaller the number the brighter it is. Is this the way round you are seeing?
Second the FETs should be turning off, make sure the ground of the 12V supply is connected to the ground of the arduino.
Sorry, I wasn't too clear about that. A Processing sketch sends values from 0 to 255, the Arduino then changes these values to gamma-corrected values from 0 to 4095.
Grumpy_Mike:
You really need an oscilloscope to see what waveform you are getting at your LED strip. It could be that the LED strip does not like a PWM power supply for some reason. It could be that it has some capacitors in that are smoothing out the PWM signal and giving it a DC voltage. This would cause it not to light at some of the low brightness values because the voltage would be less than that needed to turn an LED on. But without a scope this is only speculation.
Unfortunately I do not have one. But the LEDs do not seem to mind PWM power supplies as I can control one segment without a problem. The problems only occur with the MOSFET.
I think I just try out a different FET and see if that works. Could you have a look at this one -> http://www.irf.com/product-info/datasheets/data/IRLZ34N.pdf? This could be controlled with 5V right?