Can't rearrange Dock icons
So turns out, this problem extended to other parts in the system, namely: Xcode.
After some back-and-forth communication with Apple's support case team, the crash problem in Xcode turned out to be ibtoold and pboard processes are malfunctioning. They said it's a clipboard set of processes, and if I have any clipboard-relevant apps - they might be clashing with them.

So the only possible culprit on my system was CopyClip.

To make sure that was indeed the problem, I quit CopyClip, and restarted the processes, then restarted Xcode:

killall ibtoold pboard


And it worked. I made sure that was indeed the problem by starting CopyClip again, then running the same command again - and the problem returned. I then fixed it once more.

I figured the problem might be the same for the Dock, so I killed it:

killall Dock


And voila, it was functioning again!

TL;DR: Applications that provide special handling for the clipboard, such as CopyClip or PushBullet's "Universal Copy and Paste" collide with processes necessary for Xcode and Dock to function correctly. My problem was resolved by disabling or getting rid of that app and restarting.