Old thread, but I thought this may be helpful for those new to this (like me).
I am driving a single 16ft led rgb strip using IRLB8721 N channel mosfet's, with a 12v 5a power supply connected to the barrel jack on the uno. The VIN is connected to the +12v lead on the rgb strip. This was following the adafruit example here: Usage | RGB LED Strips | Adafruit Learning System
I was experiencing PWM led rgb flicker as well, once the duty cycle wasn't 100%. As other's have mentioned, different pins have a different frequency depending on their timer.
On Arduino Uno ATmega328P, the frequencies are defined in the previously mentioned article, Arduino Playground - TimerPWMCheatsheet.
I was originally using pin's 3 (red),5 (green) and 6 (blue) and noticed the flicker almost immediately when changing values.
The solution is very simple if you only need to drive one strip (3 pins). In my case, choosing pins with the same frequency works fine. e.g., 3, 9, 10 which all have the same frequency of 490.2. Dimming, fading, etc., all works great.
Hope this helps!