The reason that you see the problem is related to differences in the encoded files. If you have problem files, you can encode them with a older version of FLAC and they will play fine with both older and newer decoders.
I know it can be confusing, but it’s just the way it is. As I mentioned, I have old decoders that can play the files from the new encoder and some that can’t. The NSLU2 with Firefly has no trouble, and in my car I have a Phatbox – that runs FLAC 1.1.2 as the decoder and it also has no issues with files from 1.2.1. So it is not the decoder itself which is broken but the way in which is it used in the application (on the PC), or more specifically in the decoder library.
You are right in one sense – the tables in most files take little enough room. It is just some bigger files that seem to have the issue.