When you PWM the LED with the hardware PWM, you are flashing it on and off very quickly and controlling the duty cycle.
When you multiplex, you are scanning through the rows of your matrix, in effect each row is flashed on and off very quickly.
What will happen is you'll have periods of time when the off parts of the PWM match up with the off times in multiplexing a bit too much, and the LED will seem dimmer. And times when with on PWM match up with the on for the multiplexing and the LED will seem brighter.
This will make the LED appear to flicker, as you described, and the technical term for this is "beating" or "hetrodyning"
Ever notice how when you point a video camera at a CRT, you get a bright band moving up or down? It's the same effect.
You have to either synchonize the PWM and Multiplexing or use a chip like the TLC5940 which avoids multiplexing entirely. Or for 9 LEDs, just use 9 IO lines and skip the multiplexing.