You have been biten by the last paragraph of utime documentation:

Note that only passing one of the first two elements as "undef" will be equivalent of passing it as 0 and will not have the same effect as described when they are both "undef". This case will also trigger an uninitialized warning.

and you may check this is so by using -w:

G:\>perl -w -e "utime(undef, 1156817846, 'foo') #
Mon Aug 28 22:17:26 2006"
Use of uninitialized value in utime at -e line 1.
[download]

And the following seems to do something more similar to what you want:

G:\>perl -w -e "utime(-A 'foo', 1156817846, 'foo') #Mon Aug 28 22:17:2
+6 2006"
[download]

Updates:

1. as noted by belg4mit, utime docs were updated at 5.8.1 (as can be seen here: 5.8.1 utime vs 5.8.0 utime).
2. Windows has weird ideas about tracking access and modification times.

Interesting, must be newer dox. Mine just say:

Changes the access and modification times on each file of a list of files. The first two elements of the list must be the NUMERICAL access and modification times, in that order. Returns the number of files successfully changed. The inode change time of each file is set to the current time. This code has the same effect as the "touch" command if the files already exist:

    #!/usr/bin/perl
    $now = time;
    utime $now, $now, @ARGV;
[download]

If the first two elements of the list are "undef", then the utime(2) function in the C library will be called with a null second argument. On most systems, this will set the file's access and modification times to the current time. (i.e. equivalent to the example above.)

    utime undef, undef, @ARGV;
[download]

In any event, this did not address the problem:

G:\>perl -we "utime(1, 1156817846, 'foo')"

G:\>stat foo
  File: `foo'
  Size: 0               Blocks: 0          IO Block: 1024   directory
Device: 435c336ch/1130115948d   Inode: 12243914462851298397  Links: 2
Access: (0755/drwxr-xr-x)  Uid: (  400/ jpierce)   Gid: (  401/mkpasswd)
Access: 2007-02-05 00:00:00.000000000 -0500
Modify: 2000-07-14 00:00:00.000000000 -0400
Change: 2000-07-14 00:00:00.000000000 -0400

Did you test on a directory, which was what the question was specifically about?

UPDATE: Sorry, I stat'ed the wrong file when checking the new code; it doesn't help that windows only seems to track the date for access time. I suppose this is another argument for remembering to check warnings. Time for bed now,

--
In Bob We Trust, All Others Bring Data.

You could also try Win32API::File::Time