Ok, after further testing it looks like I have an answer which I'm confident enough to share with the community:
There is no one thing that will guarantee that a ship will survive (except going slow or not re-entering, which aren't really options), but there are a combination of steps you can take to minimise the chances of destructive overheating.
Having a heat shield is NOT a cure-all. It won't help you unless it's pointing in the right direction, of if you're going too fast or too steep or too heavy. But the right combination of procedures can save your Kerbal's life.
It's worth noting that most simple up/down sub orbital flights don't need heat shielding because the speeds generated aren't high enough.
Surviving Orbital Re-Entry 101
This is the combination that will help your ship survive orbital re-entry on Kerbin(It will probably also work on Eve, Duna, Laythe and Jool):
1. Have a heat shield
The heat shield is designed to save ships from re-entry from orbit. Engines also work pretty well for heat shields, but don't rely on them.
You can sometimes get away with a 1.25m heat shield on a 2.5m craft, but avoid this unless you like explosions.
2. Point your heat shield at the heat
If your heat shield isn't pointed towards the heat, it won't work. If you have a heat shield on the bottom of your ship (Like a command pod Mk1) and a level 1(or higher) Pilot, use SAS and point Retrograde. If the heat shield is on the top of your ship, point Prograde.
3. Don't enter too steep
When it comes time to re-enter, it's easiest to drop your Periapsis to 0m. Then you know where you're going to hit (factoring planetary rotation) and you can target the VAB for maximum recovery dollars.
But that is a terrible, dangerous way to re-enter. What you want to do it drop your periapsis to around 30,000m (on Kerbin) so you can ease down your speed, rather than trying to lose all your speed at once.
You also want to drop your apoapsis as much as possible too. That will reduce the amount of speed you need to lose at periapsis. You definitely don't want to re-enter hyperbolically!
4. Use parachutes
This one is so obvious. On Kerbin, chutes can open around 22,000m. The drag from partially open chutes can slow you down enough that heating effects dissipate in seconds. However, it's super annoying to have your chutes slowing you down all the way to the ground and removes some of the "realism" to open your chutes at Mach 3.
EDIT: As of KSP 1.0.1, parachutes can be destroyed if you open them going more than 1000m/s. So don't go doing this at 3000m/s and expecting to survive.
5. Keep everything stowed
I used to like to make a nice symetrical ship with mystery goo containers, batteries, solar panels and monoprop tanks on the outside of my ship. You can't do that anymore - store them in the new "Service bay" parts. I've found that you can position 4 solar panels inside the service bay nicely so they open out without clipping into things.
Even OX-STAT, the single solar panel is destroyed on re-entry if you come in too fast.