I think your gut was absolutely right. Look for interesting problems. I would then check the founders out during your interviews (they should be there if its early stage) and check especially if they are down to earth, pragmatic and make sure they wont micro-manage.
I would avoid trying to evaluate startups like a VC would. VC's themselves cant predict success and its their job, so it's unlikely you would be able to. At most you can guage current "rocket ships" by looking out for extremely (relative to round stage and vertical) large raises. I would filter out those startups set up by career finance or well-off folks, as they would be better at raising money anyway so valuation may not be related to traction. However note raising lots of money is not a garuntee of success nor does it mean it will be fun to work there.