Ask your stakeholders how accurate each estimate needs to be and how much they want to spend on estimating. Where I'm at now a simple complexity score of 1,3,5,8,13 works fine and gives us +-30% variance and predictive power for new work when translating points into time spent after about three months of work and collecting the velocity.
We spend about five minutes answering how complex is this for each story. To get a 10% variance takes the team a half day for anything non trivial. You have to go through this exercise in both extremes with the stakeholders and then you get buy in for the fast estimating.
Google Mike Griffiths cone of uncertainty for the real take on this.