Headroom:
The " standard" PWM frequency on the Arduno boards is 500 Hz. Frequencies over 100-120hz are not visible to most people.
It may have more to do with the 8- bit resolution of the Ardinos PWM signal in combination with the non linearity of the human brightness perception.In my own projects trippylighting.com I use an Led driver board http://ledshield.wordpress.com/ with 12 bit resolution, allowing me a CIE brightness corrected dimming, alas at about 120Hz (IIRC) PWM frequency. Smooth as butter dimming without any perceivable flicker.
I did a RGB LED strip controller with IR remote, I coded my own three channel PWM with 8bit resolution, I did not see flickering even thought the MCU is a 8-pin PIC12F629 running at 4Mhz (1 MIPS, though as PIC divides clock by 4). With all the looping and conditions, I think I was running it at 20KHz (not very sure because of IR decoding logic was also in the code).
I think you are right about perception -- at low intensity, a bunch of lower intensity cycles are perceived together as dark, thus the enlongated "dark" cycle that appear as flicker.
Just a hunch.