Well, I've never had any issues playing songs, but every song on my KX-5 is encoded to the exact same format/bitrate. I played around with a few variations - my KX-5 is very versatile, haven't met anything it couldn't play - and settled on 22kHz, 96k Mp3s encoded with Nero's mp3PRO encoder, in the Wave Editor application.
I would understand if you don't have Nero and don't want to pay for it, but what I would recommend in that case is, find a cheap or free encoder, find a format which works for you, and encode every song to that specification. My memory card is only 512MB, and my phone music folder is only about 250MB, so it's not a storage constraint at all.
What I don't get about the KX-5 is what tag information it needs. Sometimes it will list the artist/album information correctly, sometimes not.
And one thing I get but do not like is its ordering. It orders by modified date, or creation date. One of the two. I have a program which will change the date/time in a file, or a bunch of files. I ran it on my phone music folder, and it sorted some of the songs, but not all. I wish the damn KX-5 would sort the music by filename, or by artist name, or by song title, something that would make it easier to find stuff. And I only have about 75 songs up there.