In fact, this is one of the things that concerns me most about Obama. I too like the fact that he sounds like a reasonable man in interviews and he seems to value his opponents' aguments. But his voting record shows none of that. By his words, he is a deeply thoughtful man. By his actions, he is a hyper-partisan.
George Bush has taught me to evaluate politicians by their actions, not their words. Ironically, if being open-minded were your highest priority for a politician, then John McCain's actions (though not his words) would place him among the best of any living politician.