Measure your feet precisely before ordering Softstar shoes. Watch the video. I'm thinking about ordering a pair too. The nice thing is they'll make custom shoes if you're like me and have very wide feet or other issues with fitting into the typical shoes.
Just ran 5.6 miles on pavement with my Vibram KSOs and they were surprisingly a very smooth ride(although I had to keep my eye out for broken beer bottles on several sidewalks); I love them. Since I've worn my Vibrams I've noticed that balance has improved when I'm doing one legged dead lifts with dumbbells, but that just maybe the placebo effect.
Don't know anything about the the soft stars but I own a pair of New Balance Minmus that you might want to look into.