If you are using iTunes, right click on the song and click 'Convert to AAC' or 'Create AAC version.'
That will convert the song into a format your iPod should be able to play.
All MP3 encoders aren't the same, so the one that was used to make that MP3 might not have created a final product that works on iPod.