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();