Here's a possible solution:

#!/usr/bin/perl -w

use strict;
use LWP::UserAgent;
use HTML::LinkExtor;
use URI::URL;
use HTTP::Request::Common qw(GET);

my $links = parse_page('http://www.perl.com/');

sub parse_page {
  my $url = shift;

  #Get the base URL
  my $base = url($url)->abs->base;

  my @links;

  #Push any matching links onto the @link array
  #Only put a relative link, so we don't store
  #excessive amounts of data
  my $callback = sub {
    my $tag = shift;
    my %attr = @_;

    if($tag eq 'a' && $attr{href}[0] =~ $base) {
      push @links, url($attr{href}[0], $base)->abs->rel;
    }
  };

  #Prepare the Link parser
  my $p = HTML::LinkExtor->new($callback, $base);

  #Fetch and Parse the web page
  my $ua       = LWP::UserAgent->new;
  my $response = $ua->request(GET($url), sub {$p->parse($_[0])});

  return \@links;
}
[download]

I'll explaination of what I did:

I tried to limit the amount of data that is stored into the @links array. So instead of holding the entire url in the array, then shortening it later, I just made it relative inside the callback subroutine.

Passing in the second argument to HTML::LinkExtor said to it "Add in this base url to any relative links automatically". This simplified the callback code, because every href link passed in was absolute, I didn't have to do any error checking similar to the map you used at the end of the original subroutine.

Notice how I am accessing the first element inside $attr{href}? It's an arrayref. I think this is where you may have had problems, I know I did too, at first. But liberal use of Data::Dumper showed me the error in my ways.

In order to simplify the LWP client block, I removed HTTP::Request. Instead I used a module called HTTP::Request::Common, which generally does the Right Thing, saving a few keystokes along the way.

And finally, I returned an array reference instead of a real array. When you return an array from a subroutine, you are literally copying over each element to a new place in memory. Not to mention, that when @links goes out of scope, perl's garbage collector will be invoked, and could cause a performance penalty. By passing an array reference, I have just passed the location of the @links array back to the caller, not the actual information. It's much lighter than the entire @array, and quite speedy to pass around. Your milage may vary, but I believe it's a good habit to get into.