Following down the dependency chain, I'm seeing some packages that appear to be missing.

# yum group info 'GNOME Desktop'
Loaded plugins: auto-update-debuginfo, langpacks, presto, refresh-packagekit,
              : verify

Environment Group: GNOME Desktop
 Environment-Id: gnome-desktop
 Description: GNOME is a highly intuitive and user friendly desktop environment.
 Mandatory Groups:
   base-x
   core
   ...

Ok, the core group should be installed, right?

# yum group list available ids hidden | grep -i core
   Core (core)

Hmm, even the Core group is not installed?

# yum group info -v @core
...
 Mandatory Packages:
   ...
   iproute-3.6.0-2.fc18.x86_64                                  @fedora         
   iprutils
   iputils-20101006-18.fc18.x86_64                              @updates-testing
   ...

Why doesn't iprutils have a yum repo?

# yum list iprutils
...
Error: No matching Packages to list

So, the Core group is missing iprutils, therefore it's not fully installed, and therefore Gnome Desktop is not fully installed either.

I wonder if other groups are missing packages?

I hacked together a quick script (see below) and found the following groups are missing mandatory packages:

gnome-desktop
   PackageKit-gtk-module
   gnome-disk-utility-nautilus
xfce-desktop
   xfce-utils
sugar-desktop
   sugar-cp-all
developer-workstation
   Warning: Group/Environment developer-workstation does not exist.
infrastructure-server
   Warning: Group/Environment infrastructure-server does not exist.
basic-x-windows
   Warning: Group/Environment basic-x-windows does not exist.
minimal
   Warning: Group/Environment minimal does not exist.
admin-tools
   ettercap-gtk
cloud-infrastructure
   pacemaker-cloud
development-tools
   ipython
hardware-support
   s3switch
input-methods
   scim-mozc
multimedia
   gstreamer1-plugins-espeak
system-tools
   vbetool
anaconda-tools
   s390utils
   s390utils-base
   silo
   uboot-beagle
   uboot-origen
   uboot-panda
   yaboot
gnome-apps
   evolution-NetworkManager
xfce-apps
   clipman
core
   iprutils
   ppc64-utils
development-libs
   db4-devel
dogtag
   pki-common-javadoc
   pki-java-tools-javadoc
   pki-util-javadoc
gnome-desktop
   PackageKit-gtk-module
   gnome-disk-utility-nautilus
legacy-software-support
   compat-db
sugar-desktop
   sugar-cp-all
xfce-desktop
   xfce-utils
base-x
   xorg-x11-drv-geode
   xorg-x11-drv-omap


Quick hack to find groups with missing packages.  (The output above has been edited to make it shorter.)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#!/bin/bash

yum group list installed available environment hidden ids packages | \
    grep ')$' | awk '{print $NF}' | tr -d '()' > /tmp/yum-groups

for g in $(cat /tmp/yum-groups) ; do
  echo "~~~"
  echo $g
  yum group info -v @${g} | grep '^   ' | awk '{ if (NF == 1) { print $0 } }'
  echo ""
done
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

It looks like the problem is in the comps file.  I can see the missing packages listed for the various groups in my yum cache:
  /var/cache/yum/x86_64/18/fedora/*-comps-f18.xml.gz

I did a 'yum clean all' and verified the comps file was removed, and checked the yum groups again, and the problem is still present.

 Yeh, that's how non-object groups are supposed to work (or at least have traditionally, and it's really annoying to get the information that the packages aren't available to the bit that looks if the groups are installed IIRC).

 Sometimes I've seen this it's because the package is only available on certain arches ... but that can be worked around by playing with mandatory/default/optional or using deps. etc.

 Moving to comps.

Environment groups aren't groups; they are a list of groups.

Some of them do share the name with existing actual groups - if that is a problem, we can adjust it.

Created attachment 626074 [details]
screenshot of gnome apparently not installed

The problem is it's confusing to the end user when it appears that groups -- environment or regular -- appear as not installed.

This propagates up to the PackageKit GUI also. 
 - Start the Software program
 - go to Package Collections
 - notice that GNOME Desktop Environment is unchecked
 - click checkbox for GNOME Desktop Environment and hit Apply Changes
 - when it finishes installing GNOME, restart the Software program
 - go to Package collections
 - hey, GNOME is unchecked!  but I just installed it!

Some of that may be due to the name clash mentioned above in comment #5.

OK, I have pushed a variety of changes to comps that should make behavior better here.

1) I've fixed it so that groups and environments no longer have the same names or IDs.
2) I've edited the categories so that options available in anaconda should be available post-install.

Due to how comps work, you'll likely not see these changes clearly until all of the following have happened:

1) a new nightly tree is pushed
2) a new updates push is done
3) a full PK refresh is done

Sounds like it's long since fixed

This bug appears to have come back on my system within the last 2 days after I picked up 205 Mb of updates.

I'm running Fedora 19.  Apper shows no updates are required now, but If I run Yum update it shows the following warnings, then that there are no updates.

Loaded plugins: langpacks, refresh-packagekit
Warning: group core does not exist.
Warning: group gnome-desktop does not exist.
Warning: group multimedia does not exist.
Warning: group firefox does not exist.
Warning: group guest-desktop-agents does not exist.
Warning: group base-x does not exist.
Warning: group anaconda-tools does not exist.
Warning: group fonts does not exist.
Warning: group hardware-support does not exist.
Warning: group dial-up does not exist.
Warning: group printing does not exist.
Warning: group kde-desktop does not exist.
Warning: group libreoffice does not exist.
Warning: group input-methods does not exist.
Warning: group standard does not exist.
No packages marked for update

I just installed gnome-desktop again and still it shows it as missing.

Where could all those packages have gone?

That might be a different problem, check out whether your problem doesn't fit one of the other bugzillas we have currently open for yum groups.