I've seen this happen on a Subaru Impreza -- after I replaced the
thermosensor the problem went away.
This is the sensor that the computer uses to make mixture adjustments,
not the sensor that is hooked into the dash thermometer. The car would
always think it was hot so the adjustments were made accordingly. On a
cold start, the car would be very hard to start.

Not sure if they do the same thing on a Nissan, but it is food for
thought.

Remco