Why does the number of rows change during AIC in R? How to ensure that this doesn't happen?

From the Warnings section of ?step:

The model fitting must apply the models to the same dataset. This may be a problem if there are missing values and R's default of na.action = na.omit is used. We suggest you remove the missing values first.

So you should do:

no.na.data <- na.omit(data[c(predictors, response)])
model <- lm(formula=as.formula(paste(paste(response,'~', sep=''),
                                     paste(predictors,collapse='+'), sep='')),
            no.na.data)
step(model)

I was faced with the same problem but I couldn't use Flodel's solution because I couldn't access the original data because it was computed inside a function. I give here my alternative solution which only uses the model. Let data be the dataset with missing values:

model1<-lm(response~., data=data)
model2<-lm(response~., data=model1$model)
step(model2)

Although this way wastes some computer time, it has the advantage of just using information already contained in the model.