This is an example of one of those times when having a rigid style manual can be self-defeating. There will always be exceptions for some "real-life" situation. Naturally, they can't all be implemented. Since this one was essentially supported for a long time, since there are authors who would use it (wisely, I'm sure!), and since David has a good in-principle argument for its adoption, it seems pretty reasonable.
Random examples from "big" presses: In a Pearson proof-transition book (Chartrand et al.) there are captioned (below) Figures for truth tables, as well as many Cayley tables. And actually even a tabular-like object in a Figure to show the bijection between QQ and NN ... but Hughes-Hallett uses Tables (sometimes even titled above, sometimes blank) for short amounts of function values in a "tabular". Some other calculus textbooks actually oriented all their "tabulars" of function values vertically, just two columns, no captions/titles or even numbering (uniformly).
Finally, although the abstract algebra books I consulted had a lot of options, more had Tables than other things, but there was some variation. One Pearson text even had (are you ready for this?) Tables, Figures, and Charts (!?!) for their Cayley tables. The only consistency I saw in that one was that if there were two Cayley tables in one item, it was a Figure.
At any rate, Cayley and truth tables really are not tables in the usual sense, even granted Rob's objection to David's remark about n, and if I had a vote (which I assume I do not), I would strongly support this proposal, if only because it's an easy win for the community as a whole, as evidenced by this thread's length.