Your solenoid response time is likely to be much, much slower than the bit-banging rate of any modern uC. A standard PIC or similar would do fine (assuming it has the I/Os you need).
For driving a few dozen RGB LEDs with PWM to control brightness on each of the three channels, you're very quickly going to reach the limits of what you can do with a standard PIC. Or even if not driving the LEDs directly but using something like these: http://www.adafruit.com/datasheets/WS2812.pdf you need to be able to produce a fairly high precision 800 khz serial signal with no clock.
Between the number of inputs and outputs needed (lots of switches and sensors on the playfield, lots of solenoids to kick out balls and control various toys, lots of LEDs), and the high-speed output needed to drive the LEDs, I'm not sure a standard PIC is going to cut it, though I haven't actually sat down to calculate out the precise number of I/Os and speed that I'll need so I may be wrong. I'm more looking for a ballpark of what I should get a dev board for and start playing around with, I may wind up changing my mind and switching to something else later.
As for the WS2812, that's annoying :) It would be nice if it could use SPI or a UART. I see the NeoPixel library uses bit-banging with interrupts disabled and relies on instruction timing, yuck. But hey, it might work. I've seen single-wire stuff work on Windows CE, for crying out loud. AFAIK you don't need a continuous 800 kHz signal, you can just send it when you want to update.
Since there are probably going to be at least a few dozen LEDs, the per LED cost can add up quickly, so I'm fine with spending a bit more on a more powerful microcontroller or FPGA and learning a new system. And of course, part of the goal is to learn new things and have fun with the project, so some of these new highly parallel microcontrollers like the GA144, Propeller, XMOS, or even an FPGA would be more interesting to work with than a standard PIC, even if they may technically be overkill.
This is the first time I've done hardware hacking in a while; the last time I did it I used a 68008 as my microcontroller. So I'm hoping to find something that will be interesting to learn, not too hard to use, and capable of everything I'm going to throw at it, so I don't have to go through several iterations of buying expensive development boards only to discover that I can't drive my dot matrix display or I can only drive half of the playfield LEDs that I need or that interrupts from the flipper buttons cause my LED color fades to flicker since they screwed up the timing of my signal to the driver or something of the sort.
One of the problems is that since there are so many choices, and I haven't done hardware hacking in a while, I don't have a good sense of what I'll be able to do yet. Maybe I should start small, with an Arduino or a PIC or something of the sort, and move up if I discover that that can't do something that I want.
(And yeah, I feel dirty for blowing up a GreenArrays thread with a suggestion for a more traditional microcontroller, especially not having really studied the GA chip.)
A FPGA is extreme overkill for this, and keep in mind that you still need some CPU to drive the logic (which could be on the FPGA chip itself, but I don't think this class of FPGA is reasonably priced). A CPLD is still overkill, but at least you don't need to futz with separate configuration memory. And you'll still be doing low-level programming for reconfigurable logic, just in Verilog instead of assembler.
Your level of parallelism isn't actually very high, and I suspect a large single-thread 32-bit microcontroller will do you just fine unless you're looking for an excuse to play with something else.