I just came back from CompUSA
I told them I'd like to exchange it because the camera is defective, and they were fine with it.
But before leaving Customer Service I went ahead and tried it out, and that n800 had the same problem.
So they called some people over and we talked about it - they were thinking there was some setting or something. In the end, I just asked for a refund which they were happy to do. The manager offered to try another n800, but I didn't want to open up another box just to see that it had the same problem.

It's a shame too, I really liked the n800. I guess I'll wait a few months and try again