rhett, the flickering is indeed caused by PWM. To achieve a given level of light output, it's better to fit LEDs with much higher output, and then pulse them, rather than fit LEDs with the desired output and run them continuously. Pulsing allows the diodes time to cool, and so prolongs their working life.
As for how to fix it.. With a good quality video camera, you can remove the effect by choosing a slower shutter speed (and controlling exposure with a tighter aperture or a neutral-density filter over the lens), at the expense of some motion blur. On a phone camera, there's nothing you can do about it generally - I've never seen a phone camera with video shutter speed control (although the best cameras like Nokia's will allow shutter speed control for stills)