Well, I don't think this is due to swapping.

I have a CPU and Memory applet installed which shows the current CPU and Memory used as a bar in the status bar, and neither is near the maximum.

Another evidence against load/swap:
Starting a application which was unresponsive on the Desktop from the "Application Menu" works right away.

So in my opinion something prevents shortcuts on the Desktop to be executed.