http://conductiveresistance.com/arduino-starter-kit-comparison-chart/
Has a great review of many starter kits.
A related question is whether you want to do"Breadboard" based circuit prototyping, or use "Electronic Bricks" which are easy to connect to Arduino to start with but are somewhat more expensive.. Here's a link to some info on that option (This is a VERY unpublished Website, so please don't forward this link!)
http://internationalschoolphotos.com/arduino-direct/ElectronicBricks1.htm
One seller is SeeedStudio. See here:
http://www.seeedstudio.com/depot/electronic-brick-starter-kit-p-506.html?cPath=1...
(Search on BRICK on that site). Also many ebay sellers in China.