Are we talking bending laterally or vertically??
If we're talking vertical bend (i.e. Outline, headset, "on-the-bit", etc.), you need lateral suppleness before vertical. I wholly agree with Chiilaa on the progression and necessity of working from behind. The head is the hood ornament, and if the horse is working correctly from behind will fall into the correct "set" on it's own. The "headset" is a result of correctly training the rest of the body.
If we're talking about lateral bending, as I initially assumed, the first step is to rule out any physical reason for the horse to be stiff and resistant to bending, any reason that bending while moving forward would be uncomfortable. Check yourself, and the way that you cue for a bend or a change in direction; are you as a rider allowing the bend? Bending isn't achieved through the action of the hands alone... the seat, legs, and the rest of the aids come into play as well, no matter what the discipline. The bend doesn't come from the neck alone, either. A correct bend around a turn involves the entire length of the horse's body. Here's an article that gives a detailed explanation of the aids for achieving the correct bend through a corner.
Lesson 6 - on the aids - Classical dressage
Practice lots of correct turns. Figure 8's, serpentines (3-loop to start, moving to 4 or 5 loops as he becomes more supple), 20 meter circles. Try a long, shallow S bend down a long straightaway. No leg yielding, be sure that he's bending through the length of his body, and no dropping of the inside shoulder.
Best of luck!