“The number of story points associated with a story represents the overall size of the story. There is no set formula for defining the size of a story. Rather a story point estimate is an amalgamation of the amount of effort involved in developing a feature, the complexity of developing it, the risk inherent in it, and so on." - from Agile Estimating and Planning by Mike Cohn.
In my development team we estimate stories in terms of size and complexity. The way I describe it to new team members is to consider size and complexity as two orthogonal axis on a graph. This allows stories that differ in complexity, but equally differ in size (effort) in the opposite direction to be considered relatively the same.
From personal experience, we found that if only complexity is considered then your team may unintentionally underestimate stories that require large amounts of effort to deliver. This will eschew your backlog estimates and makes it more difficult to use techniques like triangulation to keep estimates relative.