I would strongly caution against making him change his character. A player's only "toy" in the world is his character; taking that away because you don't like his roleplaying is rough.
Further, some people enjoy combat. Some people enjoy drawn-out political discussions. I think that you should explain to him that both of these are OK, and that he should back off a little bit when the other type of gaming is going on.
But, as I've said elsewhere, the difference between wargaming / powergaming and roleplaying is a false dichotomy. People can do both. And blaming someone because he is not as smooth a talker as his 21 Cha paladin is pretty rough. How many of us are as strong, fast, smart, or beautiful as our D&D characters? (Ok, fine, yes, I'm the prettiest of them all, but you get the point.

)
Point to take home: Explain that there are two different styles, and that both need to have a place in the game, not just kick-in-the-door. But then let him know that booting head and taking names is a part of the game, and that you appreciate his contributions to the tactical side of the game.
best of luck,
Carpe