I got interested in the lyrics.
They were written by Don Raye, who also wrote the lyrics to such hits as "Beat Me Daddy, Eight to the Bar", and "Cow-cow Boogie".
I think the music to "Solid Potato Salad" was by his usual collaborator, Gene de Paul, but not sure of that.
Nat King Cole also recorded the song - with more boogie than Andrews Sisters swing to it.
Still don't know just what was meant by the term "Solid Potato Salad", but Raye also used the term in another song, as "four solid". My guess is that at the time the term "solid" was slang for "real". It's still used as slang today, but more to indicate a favor, as in, "Do me a solid".