Fisher exact test is said to be used with a total sample (n) < 1000, whereas chi-squared test should be used when each category (/cell in a contingency table) >=5. What if you have an mxn contingency table where the total sample size > 1000 but some of the cells have 0 or 1 sample size?
How far above 1,000 is your sample size? If it's not far above 1,000, you can use Fisher's exact test - it's simply recommended that you don't because of computational limitations.
If Fisher's exact test is too computationally intensive and you need the chi-square test, would try to "bin" the variables differently. That is, collapse categories until you have at least 5 in each cell. You could, alternatively, use Yates' correction to account for the undercounts in certain cells.