Seems to just be a timeout issue on resolving shortcuts.
Removing any shortcuts that take a long time to load fixed the explorer crash for me on Windows 7 x64.
Note that these shortcuts need to be removed from the desktop entirely. It is not just the shortcuts that are in fences, and it also causes the snapshot (e.g. when it takes a snapshot during installation) to take a long time and potentially time out.
For example, dead links (shortcuts to locations that do not exist), network shortcuts (e.g. \\192.168.x.x\path\to\wherever), shortcuts to mapped network drives, possibly shortcuts that use URI style protocols (http://, irc://, steam:// etc) and possibly shortcuts to other non-file objects such as printers.
To test if this works for you, you can just disable fences then make a new folder on the desktop and drag everything else from the desktop into it before starting fences to see if fences starts without issue.
Still looking for where to bug report this issue with fix.