You could upsample them for the player. Dump them to WAV, then re-encode them at a higher bitrate. You won't increase the quality of the files (in fact, you will decrease the quality very slightly), but at least they'll play correctly.

Keep in mind that it's unlikely to be the bitrate that's the problem. More likely, it's the samplerate or bit depth that's the problem. For instance, the player shouldn't have any trouble playing back a 44khz 16-bit stereo file even at painfully low encoded bitrates. However, if you try to play a 8khz or 11khz mono file, regardless of how well-encoded it is, then it's got to do samplerate conversion on-the-fly up to 44khz 16-bit before it can play back the audio. The player's samplerate converter probably just isn't as well-optimized as the one on your PC.

The trick is, when you dump your low-samplerate files to WAV, you have to make sure to do it into 44kz 16-bit stereo with something that does a good job of samplerate conversion. Perhaps TotalRecorder can help in this situation?