TL;DR: Adding the user to the sudo group with sudo usermod -aG sudo username solves this problem because both sudo and Polkit use that group.
The usual and expected way to give a user administrative powers on an Ubuntu system is to add the user's account to the sudo group. This gives them powers not just through sudo but through Polkit as well. The graphical prompt that lets you select between users with administrative powers is a Polkit prompt, not a sudo prompt. As muru says, most graphical programs that prompt you to enter a password to perform an administrative task are using Polkit, not sudo.
But to make a user an administrator, to allow them to perform actions as root with sudo and Polkit and so that they will appear in the list of users to authenticate as when using Polkit, you do not need to configure sudo and Polkit separately and I recommend against doing so. Just put the user in the sudo group. Don't be fooled by the name--Polkit respects this group just as sudo does.
The wording of your question very strongly suggests that, rather than adding the user to the Polkit group, you had added a custom entry for that one specific user in /etc/sudoers:
...it just specifies it as the user that set up my machine.
The user created when you install Ubuntu is added to the sudo group.
And you mentioned (emphasis mine):
And user Y is in the sudoers file and as of now user X is not.
Polkit does not use /etc/sudoers so giving a user the ability to run sudo by editing that file does not give them abilities through Polkit. That's a possible reason you might actually want to edit that file--if you wanted to give a user powers through sudo but not Polkit. However, you want both, and that's what the sudo group in Ubuntu is configured for already, so you should just use that.
Since you do have the ability to run commands as root with the sudo command, you can add username (replace it with the actual username, of course) to the sudo group by running:
sudo usermod -aG sudo username
Or if you want to use Polkit to add it, you can run this command, which has the exact same effect once it completes:
pkexec usermod -aG sudo username
After you run either of those commands, username will be able to perform arbitrary actions as root through both sudo and Polkit. Note that usermod needs the -a flag, as shown, or it will remove the user from other groups, which you do not want.
See also How to add existing user to an existing group?
In case you're interested in how both sudo and Polkit are set up to grant rights to users in the sudo group, the answer can be gleaned from their configuration files. By default, /etc/sudoers includes these lines:
# Members of the admin group may gain root privileges
%admin ALL=(ALL) ALL
# Allow members of group sudo to execute any command
%sudo ALL=(ALL:ALL) ALL
/etc/polkit-1/localauthority.conf.d/51-ubuntu-admin.conf consists of:
[Configuration]
AdminIdentities=unix-group:sudo;unix-group:admin
Thus both sudo and Polkit are configured to confer administrative privileges to users who are in either or both of the admin and sudo groups. The admin group is listed for compatibility with old versions of Ubuntu where admin was used instead of sudo, in case you upgrade from such a version and have user accounts in admin but not sudo. But aside from that situation, you likely don't even have an admin group. Running getent group admin sudo will show which of those groups exists and which users are in them. On a freshly installed 14.04 system, it won't show anything for admin. So use the sudo group, not the admin group, to make users administrators.
These configuration details are true of Ubuntu 14.04, as you were running when you asked this question, but also of all subsequent releases as of this writing, up to and including Ubuntu 17.10. Adding a user to the sudo group is the fully effective and most appropriate way to give them full sudo and Polkit powers, on all currently supported Ubuntu releases.
I'd like to acknowledge Videonauth both for the useful comment on another answer (that has since been deleted) that led to my writing this answer and for verifying that the information I've given about the contents of sudoers and 51-ubuntu-admin.conf is still accurate as of Ubuntu 17.10.
