Quadrilla marble toy is excellent, if a little pricey. It's a real wood marble run, very stable, and each color of block has a specific purpose. Once you figure out the system, you can build some wonderful complex towers for the marbles to run down.
We didn't get it for DS until he was 3, due to the small marbles, but he'd been begging for it for at least 6 months prior to that. He'd seen one set up at a toy store and fell in love with it.
I have a feeling that the Rokenbok (sp?) system is going to be next on his list, so I guess we'd better start setting money aside now. :P