SilentGhost's analysis is correct.  The provided example code causes the error because it is trying to move the symlink into its target when the target is a directory. Any cross-device moving issues are unrelated to this example code.  Here is the relevant code in the master branch:

    if os.path.isdir(dst):
        if _samefile(src, dst):
            # We might be on a case insensitive filesystem,
            # perform the rename anyway.
            os.rename(src, dst)
            return

shutil._samefile() considers the example link and its target to be the same.  When _samefile() returns False, this code gets executed:

        real_dst = os.path.join(dst, _basename(src))

        if os.path.exists(real_dst):
            raise Error("Destination path '%s' already exists" % real_dst)
    try:
        os.rename(src, real_dst)
    except OSError:
        if os.path.islink(src):
            linkto = os.readlink(src)
            os.symlink(linkto, real_dst)
            os.unlink(src)

A simple fix is to check whether src is a symlink when _samefile() returns True.  The "Destination path...already exists" error isn't a problem for our symlink case because the shell mv command also returns an error.

$ ls -l /tmp/tmpdir/
total 0
lrwxr-xr-x  1 jeff  staff  11 Aug  5 23:36 test_dir -> /tmp/tmpdir
$ mv test_dir /tmp/tmpdir
mv: test_dir and /tmp/tmpdir/test_dir are identical

I will generate a pull request.