I suppose you've made sure it's not just dirt on the sensor, have you? Or is it obviously not that?
I had my sensor cleaned professionally, then never changed the lens I put on but still managed to get some dirt on. This would be quite possible if you've been changing lenses, no matter how careful you are.
You could ask the store to look at it and see if they will send it back to Nikon as it's still under warranty.