rmdir works fine for me. What error does rmdir return?

C:\>dir /s/b test
C:\test\sub
C:\test\sub\a

C:\>perl -e"unlink('//tribble05/c$/test/sub/a') or die $!"

C:\>dir /s/b test
C:\test\sub

C:\>perl -e"rmdir('//tribble05/c$/test/sub') or die $!"

C:\>dir /s/b test
[download]

Update: I meant to say: Are you sure you aren't trying to remove a directory in which you are current chdired?

I have found ways to do this using system commands, but I would prefer to do this within Perl

Why? Do you have lots of UNC paths to remove? This:

perl -MTime::HiRes=time 
-wle"print time; system q[rd /s /q \\.\test\delete_this]; print time;
1201559494.81249
1201559494.82497
[download]

Takes all of 12 milliseconds to execute and consumes a whole extra 2k* of ram for that brief period.

*Assuming you started the script from a command line.