Juste au cas où vous ne voudriez pas réinitialiser votre téléphone. Ajoutez un nouveau compte gmail en allant dans Paramètres --> Comptes --> Ajouter un nouveau compte. Ajoutez votre compte gmail. Une fois que vous êtes connecté, lancez votre application Google playstore. Cliquez sur le menu (en haut à gauche, il ressemble à 3 lignes horizontales empilées), vous verrez votre ancienne adresse e-mail, cliquez dessus et sélectionnez votre nouvelle adresse e-mail. J'espère que cela devrait faire l'affaire.
EDIT : Pour supprimer votre ancien compte, lancez les paramètres -> sélectionnez les comptes -> sélectionnez Google -> sélectionnez le compte que vous souhaitez supprimer -> cliquez sur les options en haut à droite (ou sur la touche d'option matérielle si votre téléphone en possède une) -> tapez sur supprimer le compte.