Before you get too panicky, there are a couple of things to keep in mind. The first is, as suggested already, you may have missed a setting (exposure compensation). That may not be the problem, though, since you're only experiencing the problem in very bright conditions.

That brings us to the second: to an extent, the camera is supposed to do this in Auto. You said that 1/4000 and f/4.5 at an ISO of 200 gave a good exposure in manual mode. That's really, really bright—about a full stop brighter than "sunny 16" would predict. It may (just may) be bright enough to push the camera's exposure program into its beach/snow territory, where the camera assumes that the only way there can be this much light coming in is if the scene is far lighter than average. That's the sort of thing that happens if the foreground is largely either white beach sand or snow, and the camera is actually designed to overexpose under very bright conditions to compensate (otherwise a picture taken in a snowy or white-sand setting would tend to be significantly underexposed).

As long as the camera is exposing properly under other conditions, it's probably doing what Nikon intended. If you can keep the "sunny 16" rule in mind (the shutter speed should be about 1/ISO at f/16 in clear midday conditions), you'll have a sanity check on the values the camera reports, and will know either to use exposure compensation or alternate metering to get the shot.