I had to make a few changes to get this to compile, but when I did it worked correctly:

#!/usr/bin/perl -w

use strict;

my $pathToFiles = '/home/pencilneckgeek/files';
my $tempDir = '/home/pencilneckgeek/tmp' . rand(10000);

mkdir($tempDir, 0777) or die "mkdir: $!\n";

$origFile = "$pathToFiles/theFile.txt";
$theLink  = "$tempDir/theFile.txt";

symlink($origFile, $theLink) or die "symlink: $!\n";

  # do some stuff...
  ...
  # now, here's where the problem lies...

unlink($theLink) or die "unlink: $!";
[download]

First, I used the concatenate . operator (see perlop) instead of addition to create $tempd. Then, I gave mkdir a mode for the new directory. It fails otherwise.

Things worked fine after that.

One troubleshooting tip. I always like to print variables (or look at them in a debugger) when things fail suddenly. This should help: print "theLink is set to ->$theLink<-\n";