Some MP3 players aren't designed to handle bitrates outside of a certain range, i.e., some can only handle 64-192 kbps MP3s. If you right-click on the MP3 properties, what does it say the bitrate is?
Also, there's different kinds of bitrates: constant bitrate (CBR), variable bitrate (VBR), and average bitrate (VBR). If you play these in Winamp (or many other players), you can see that the number "jumps around" a lot if it's VBR or ABR...it's higher at more complicated parts of the song and lower at less complicated parts. That way you're not wasting space if there's silence, for example.
I really have no idea what the problem is with your players, especially since they play fine on your computers and they aren't copy-protected. My only guess is it's a bitrate issue. Look in the technical specificatoins of your user manual, and maybe it'll say what your player can handle.
MP3 just stands for MPEG 1, layer 3 audio. That's what it is.