What I suggest you use is a family of 8255
Programmable Peripheral Interface chip ($5 From Jameco).
Essentially, what an 8255 gets you is 24 bits of I/O from 8 pins on your processor. (An 18F8722 has I believe 8 ports of I/O or 64 lines, so, if you really wanted to just with one level of multiplex, one 8255 chip per port, you could run 192 led's). The interface is REALLY simple, just sit down with the
data sheet and about one cup of coffee (or tasty beverage of your choice) later you should have enough knowledge to go out and hook up an 8255 to your processor of your choice.
Of course, if 192 output lines isn't enough, you can just add another level of multiplexing (1 byte I/O from processor => 1 8255 Chip => One 8255 chip for each byte on the previous=> 9 bytes of I/O per 1 byte of processor I/O (or 72lines per every 8)). So, if you added one more level of multiplexing on all of those ports you'd still EASILY make your update rate with the 18F8722 (or other 40MIPS+ processor) and be able to run up to 576 led's.
BUT! Remember to put resistors in series with your leds or you'll easily go over the 2.5mA per line drive current. You'll most likely need a darlington array IC to drive your LED's in the end if you want bright ones... but thats another story which i'll write if there is interest.
Have fun! Sounds like a fantastic for-the-heck-of-it-project!
-q