Please try to include stack trace in bug reports. I reproduced the error
on my Linux (SuSE 10). 

marvin:tmp$ ls -l dirlink testdir
lrwxrwxrwx 1 raghu users    7 2007-12-20 10:10 dirlink -> testdir/

testdir:
total 0
-rw-r--r-- 1 raghu users 0 2007-12-20 10:36 testfile

shutil.rmtree('dirlink') produces:

----------
Traceback (most recent call last):
  File "t.py", line 4, in <module>
    shutil.rmtree('dirlink')
  File "/localhome/raghu/localwork/cpython/python/Lib/shutil.py", line
194, in rmtree
    onerror(os.rmdir, path, sys.exc_info())
  File "/localhome/raghu/localwork/cpython/python/Lib/shutil.py", line
192, in rmtree
    os.rmdir(path)
OSError: [Errno 20] Not a directory: 'dirlink'
----------

While we are removing the contents of the target directory as expected,
the final 'rmdir' fails on removing the symbolic link. For the sake of
consistency, we can explicitly remove the target directory and leave the
symbolic link intact. Is this what you are expecting?