Perl 5.8.7
Does the script you're testing with have the suid bit set? I don't think it's stricly a taint problem. Initially I also thought it was an issue with passing tainted input so I put debug warnings in rmtree(). The first path value (passed in from the application) was taint free through the first chdir call. The subsequent recursive calls to sub directories as found and sanitized by File::Path then died.

I noticed that File::Find also had issues like this and they've added an untaint flag to the interface. The File::Find code swaps between two variables (which File::Path doesn't) when untainting and doesn't appear to suffer from the bug as a result