Many shortcuts don't work for the first time. For example I have bound "display home folder" on Win+S combination. After I log in, it almost every time doesn't work the first time I press the combination. Nothing happens. When I press it again, Nautilus window pops up. But this happens not only after log in, but also after some time - I really don't know how long, it can be 30 minutes, maybe more. Then it again doesn't work for the first press, works on the second press. 

Similarly (and more substantially) this also happens for clipboard shortcuts. I'm going quite mad that Ctrl+c/Ctrl+x doesn't work so often. I experience it at least several times a day (all in one session), maybe even several times an hour(!). Ctrl+c just does nothing, only after second (or third) press is the file finally copied to clipboard (which you can determine by looking at the Nautilus status bar).

I see these symptoms on both Ubuntu 9.04 and Fedora 11, it is not distro-specific. Also I can vouch for not having broken keyboard, because I see this on several different hardware setups.

Annoying is that it is very hard to reproduce. It just works most of the time, but when you are not trying it for a long enough, then it just doesn't work for *once* and works again. This issue is one of the most pains I currently notice in Gnome.