I have the same problem in my NX. you'll have to buy some new parts, unless you want to go through the process of rebuilding the parts.
there are 2 culprits, the Air Regulator Valve ($90.62 @ nissan) and the Idle Air Assembly, which has the main idle air solenoid and FICD solenoid on it, along with the idle screw. You can purchase a new idle air assembly at your nissan dealer for $159.10 - or you can check out
www.se-r.net/engine/cold_idle_fix.html and see for yourself. sucks to hear about the