Since the only other answer doesn't really "fix" the issue, just acknowledges it, I think it's worth saying I had this same issue, and discovered the problem.
The issue for me was relative vs absolute symlinks. I use Link Shell Extension.
When creating absolute symlinks, Explorer works fine. When creating relative links, Explorer chokes on them.
I can only guess that this is somehow related to how Explorer calculates the working directory? Maybe some slash problems?
(Note that on Win7 x64, at least, you may have to open LSEConfig.exe after installing the extension, and toggle Absolute and then Relative to get it to make relative links, as the default config is somewhat unpredictable, sometimes relative, sometimes absolute.)