ok, sorry to rebump and old post but I also encountered this very issue and found it annoying enough to fight it tooth and nail...
I think I won ;)
and the solution for me, was to force phase-correct PWM mode on timer0, based on this article: https://www.arduino.cc/en/Tutorial/SecretsOfArduinoPWM
(I was using pins 5, 6, 9 on an ATmega328P, 5+6 being controlled by timer0)
of course, that means that milliseconds now last twice as long ;) but I can live with that ;)
maybe it will help someone who has the same kind of problem...
btw, the flickering does seem to depend on the current drawn (as it was way less noticeable and sometimes completely unnoticeable with a shorter strip) but even though my LED strip draws ~1.5Amp, even buying a 5Amp power supply for it didn't solve the issue before I tried the timer tweak.