http://www.bnrobotics.com/ http://www.resquared.com/ http://www.aethon.com/ http://www.redzone.com/ http://www.seegrid.com/ http://www.bostondynamics.com/ http://www.irobot.com/ http://www.cyphyworks.com/ <-- started by some of the original iRobot folks http://www.mobilerobots.com/ http://www.willowgarage.com/ http://www.evolution.com/ http://www.sensiblemachines.com/ http://astrobotictechnology.com/ ... etc ...
NOTE: Some of the companies are further along than others but all of them (to the best of my knowledge) started as startups and/or university spin-outs (which is a subset of startups). You can normally find startup robotics companies near/around the schools with the best robotics programs (i.e. CMU, UPenn, Stanford, MIT, etc.)