This comment on the apple subreddit led me to this thread where people discuss this issue in relation to an application called Cinch. In the thread about this on the apple forums, people mention several other applications that might be causing this issue too.
What is causing this issue?
From what I can gather, this issue seems to be related to applications using Event Taps (an API that lets applications directly listen for keyboard and mouse events). I think there is either A) a bug in OS X where Event Taps sometimes stop working for whatever reason, or B) application programmers consistently have a hard time using Event Taps correctly.
What can I do about it?
If this is indeed caused by an OS X bug (this seems the most likely to me), this issue can't be fixed completely by end users. There is one thing you can do that might make it happen less frequently though: In the Cinch thread, there is a link to an application that lists all running applications that have Event Taps open. It looks like this:
I figure that the more applications you are running that have an Event Tap open, the more often you'll end up with a clogged Event Tap somewhere, and you'll have the spaces issue happen more often as a consequence of this.
So, if you're having this issue, try running as few of the applications that show up in EventTaps.app as you can.
For whenever the issue does happen, kill the Dock using whatever method you find most convenient. I keep the AppleScript snippet that Chris R posted in his answer in an .app on my Desktop, and run it whenever spaces locks up.