Unfortunately I can't find the right resistance to be able to make use of all 256 brightness values I send to the TLC.
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.
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.