If you just got it, and it is indeed a new phone I recommend just saving yourself the fuss and returning it. You can reinstall the GAPPs which include the play store, but usually that task only comes into play when flashing new ROMs.
Hope this helps!