I have had a similar problem recently under Windows Vista Business. Could not get it to work for shortcuts to a folder. It all looked OK but did not actually go to the folder when opened, just popped up the dialog asking which application to use. In the end I stopped using Wind32::Shortcut altogether. I do this instead, with appropriate definitions for $linkname and $target:

use Win32::OLE;
my $WShell = Win32::OLE->new('WScript.Shell');
my $sc = $WShell->CreateShortcut("$linkname.lnk");
if ( -d "$target")
{
    # This looks weird but is the only way I could make it work.
    # A straight forward link to a folder sort of looks right but
    # doesn't actually work when you try to follow it.
    # This creates a bit of mix between a link and a url.
    # It is a .lnk file but it sets TargetPath to a URL like value.
    $sc->{'TargetPath'} = "file:///$target";
}
else
{
    $sc->{'TargetPath'} = "$target";
}
$sc->Save();
[download]