Considering you were warmer sleeping on your back, than on your side, your problem is NOT the sleeping pad. The more surface area you put on your pad, the more the pad contributes to your overall warmth.
The problem is solely due to drafts. I've found the same problem with quilts when used without a bivy. I've found that quilts only really work well for me down to about 35 degrees. Any colder, and draft elimination is necessary. I chose a 20 degree ZPacks bag, coupled with a 45 degree quilt that I can take down to 40 degrees with a down jacket. I can also unzip the Zpacks bag and use it as a quilt during warmer temperatures to bridge the difference.
Not all side-sleepers have problems with drafts - it all depends on how restless you are. I tend to toss and turn when I'm awake, but sleep without moving much. A quilt works fine for me in warm weather, since once I fall asleep, I won't wake up from being too cold (because I'm no longer introducing drafts from tossing and turning). But in colder temperatures, the drafts from all the tossing and turning while waiting to fall asleep keeps me too cold - it's simply too cold for my body to comfortably recover from.