your problem sounds like a software timing issue and just a common attribute of human vision called persistance
the faster you scan your matrix, the less time the LEDs stay on, which means the less time your eye and brain have to integerate the light emitted. the other side effect is the leds which are actually "off" still look like they are on, because the eye and brain haven't realized the led has turned off.
there are two ways to combat the dimming of leds, first, push your LEDs with as much current as they can handle - since they'll only be on for a short fraction of a second, this will help squeeze every last drop of brightness from them. second, add a small delay, I found a good delay for my matrix by using some buttons with my microcontroller, each press would increase the scanning speed (decreasing the delay)... I adjusted it to a number that gives me the most brightness but still fast enough to not notice a flicker (from the updating)
to help with the apperance of more leds being on is also solvable in software... think of each 'update' you do to your array as a 'frame' - if you just flash each frame once on the array, your eye and brain might not have enough time to integerate the pattern clearly. try updating your array several times with the same data, before moving onto the next 'frame', each update gives your brain a little more information about the pattern it is seeing. depending on how big your array is and how complex the data being displayed is, you may only need to do each 'frame' twice, or you might need to do each ten times.
I hope this is some help to you - I'm new to LED matrices as well - I have some pcb layouts drawn up and plan to make some 8x8 display modules this upcoming weekend. I've written about what I'm up to on my blog, you can read about the 8x8 matrix
here and continued
here.
ttyl!