I believe the root cause is as described here:
Some Windows users whose Python is 64-bit have found that the PyCrypto dependency winrandom may not install properly, leading to ImportErrors. In this scenario, you’ll probably need to compile winrandom yourself via e.g. MS Visual Studio. See #194 for info.
I've been able to resolve the issue by downloading and installing a PyCrypto binary from Michael Foord's website and then re-installing Fabric. Many thanks Michael!