A Nissan/Infiniti specific board with good info is
http://forums.maxima.org .
The VQ30 has an ambient air temp sensor in the intake tract. It's in the black plastic tubing that enters the bottom of the air filter box. However, according to the FSM, it is for diagnostic purposes only. It is not used for engine operation (which negates part of #4 below).
According to the Haynes Manual, check the following:
1. Air filter clogged
2. Fuel not reaching the injectors.
3. Corroded battery connections, especially ground.
4. Faulty coolant temp sensor or intake air temp sensor.
Seeing as you've all ready replaced the coolant temp sensor, I doubt #4 is the issue. Having had 2 VQ30's, I can say the grounds (#3) are a distinct possibility. Especially on an 11 year old car. The primary engine ground is on the driver's side, front side of the engine block. You can trace your battery's negative cable to find it. It also attaches to the fenderwell below the air filter box. These would be the first 2 I check. The next I'd check is the fuel injector grounds on the intake manifold collector. There are two wires going from the wiring harness that runs along the top of the engine to the aluminum intake manifold. Be careful with these ones, as the bolts are cheap and they thread into aluminum. There are also other grounds on the driver's inner fender and passenger fender beside the coolant recovery tank (2 there). With these grounds, I'd pull each one, clean the area, and snug them back down. These bolts are 10mm, and prone to break if torqued to much. Snug is all it takes.
When I had my '96 Maxima, there was a recall on some emission parts. Something along the lines of an evaporative emission purge control valve or similar. I can't remember the specifics, but the dealership did it for free. I didn't have any driveability issues, so not sure if that would be your problem. But with your symptoms, the emission control system is a possibility.
Hope this helps.
Dave