Grounding problem? (Negative battery clamp & negative battery cable, main body ground, thermostat housing ground, engine ground, transmission ground) Bad ground could limit the electrical current needed to heat the O2 sensor. Corrosion in wiring connections is another possibility.

Take care,
ChrisS