Is there a break in your data list? Autofilter will only select data below
the heading until it reaches a blank row, unless you select the entire list
before selecting autofilter.
I just tried Autofilter on over 6000 entries in one of my workbooks with no
problems. Not sure what's causing yours, sorry. I'd have to see the
spreadsheet.