The camera's clock is powered by an independent, rechargeable power source, which is charged as necessary, by the main battery. It can also be charged, if you have purchased a Power Adapter EH-5b and Power Connector EP-5A, when the power adapter is connected to the camera, as will the main battery.
If the camera displays a warning every time, at startup, stating that the clock is not set the clock 'battery' is either faulty or there is a loose connection so as to prevent it from being charged.
The clock 'battery' is not user serviceable, (I believe it may be a capacitor soldered onto a circuit board). As you state that the camera is new your only option, I believe, is to check the warranty statement in the documentation that came with the camera and follow what it states to do in regard to making a claim for a warranty replacement or repair.