It seems unwise to do Fisher's exact test with ordinal data - you throw away so much of the information.
It's possible to do exact tests by using some statistic that incorporates ordinal information.
Expected cell counts less than 5 shouldn't be a problem - expecteds that are fairly similar can go down a fair bit smaller and still get an an adequate chi-square approximation (or you could simulate the distribution, or even do an exact test based on the statistic) -- but you shouldn't do a Pearson chi-square either because it also ignores the information in the ordering.
A useful thing to do is choose some reasonable statistic that measures the anticipated kinds of relationship between group and the ordered categories if the alternative is true (there are a number of good ways of measuring such dependence) and build a test one that, either one based on simulating from the tables under the null (possibly with conditioning on some of the sample information), or by enumeration of the tables in the tail.
One might, for example, use some measure of ordinal-nominal association, or compute something like a Kruskal-Wallis statistic (but not use the usual tables, since there are heavy ties, which must be accounted for; the distribution under the pattern of ties might be computed), or one might assign scores to the categories and apply a more typical location test, or some might look at something like ordered logistic regression (there are a variety of suitable regression-type models for ordered categorical reponses).