i agree with the other poster. Nissan is at the bottom of reliability list of jap manufacturers.
#1. i sure hope its under warranty, because if it isnt, never take it to a mechanic or dealer if you have a check engine light on. You always want to take it to an autopart store, then if you cant fix the thing yourself, take it to a mechanic... not the dealer. when you take it to the mechanic, and he tells you what needs replaced you already know what the diagnostic codes were from autozone, so he cant try screwing you over by telling you theres alot of crap wrong.
#2. I do not think the dealer was trying to screw you. There are many times when you have conflicting codes, and replacing one part, can fix both codes, and also give you another code. Its not unusual. Sometimes you can get codes where it says you have basically a fuel leak and bad 02 sensor, but fixing the leak, will cure the 02 sensor. And if you have multiple codes, replacing the cheapest part first may not fix both codes.
#3. When you look up a cars reliability, dont just go by what people in epionions.com say. That may be one good source, but you should also look up a cars technical service bulletins (TSB's). The tsbs are written by dealer mechanics for issues they are seeing with new cars. when you hear of a company having a voluntary recall, they base the recall off the tsbs.
You also need to realize, that you cant just base a reliability report off an older model. The xterra was redesigned in 2005, so you get an entirely new vehicle, so a 2004 reliability report basically means nothing. its like trying to find out if the 2007 mustang is reliable by looking at the 1976 pinto.
there are dozens of sites that lists a cars tsbs. http://www.mycarstats.com/ will give you just a basic overview, and they are usually up to date.