16kbps files definitely do not work.

MPEG-1 layer 3 defines bitrates from 32kbits/s to 320kbits/s. Any bitrate below 32kbits/s has to be encoded as MPEG-2 (or Fraunhofer's "MPEG 2.5").

Perhaps "sufficiently old" decoders only grok MPEG-1, not MPEG-2 (the data formats are the same, just the frame headers are different). http://www.iis.fhg.de/amm/techinf/faq.html

So in summary, try not going below 32kbits/s (or, for similar reasons, 16kHz sampling).

Peter