Strange failure with Spaces?
I eventually managed to find the issue by poking around in console. I got the following error messages:

Dock: kCGErrorIllegalArgument: _CGSFindSharedWindow: WID 6963
Dock: kCGErrorIllegalArgument: CGSGetWindowTags: Invalid window 0x1b33
Dock: kCGErrorIllegalArgument: CGSGetWorkspaceWindowGroup
Dock: kCGErrorIllegalArgument: CGSGetWindowOwner
Dock: kCGErrorIllegalArgument: CGSGetWindowBounds
Dock: kCGErrorIllegalArgument: CGSSetWindowListSystemLevel: Failed
Dock: kCGErrorIllegalArgument: _CGSFindSharedWindow: WID 6963
Dock: kCGErrorIllegalArgument: CGSGetWindowTags: Invalid window 0x1b33
Dock: kCGErrorIllegalArgument: CGSGetWorkspaceWindowGroup
Dock: kCGErrorIllegalArgument: CGSGetWindowOwner
Dock: kCGErrorIllegalArgument: CGSGetWindowBounds


While I'm not positive what causes these, sure enough, restarting the Dock using killall Dock did the trick. Though I still have no idea what causes this in the first place, this is at least a fix for the rare problem.