To make this diff really small, I don't care. If system fails, Module::AutoInstall will install module from CPAN (because it's not installed by system).

However, this approach has few problems: you might need to remove inc/ directory so that M::I will re-create it with this changes, and it will download only Debian packages which are required by current module (one which you did perl Makefile.PL for) and not for dependencies. So, let's move this idea at better place -- into Module::AutoInstall:

--- /usr/share/perl5/Module/AutoInstall.pm    2007-10-31 11:34:27.0000
+00000 +0000
+++ AutoInstall.pm    2008-03-13 14:48:31.000000000 +0000
@@ -6,7 +6,7 @@
 
 use vars qw{$VERSION};
 BEGIN {
-    $VERSION = '1.03';
+    $VERSION = '1.04';
 }
 
 # special map on pre-defined feature sets
@@ -287,7 +288,10 @@
             push @installed, $pkg;
         }
         else {
-            push @modules, $pkg, $ver;
+            my $deb = 'lib' . lc($pkg) . '-perl';
+            $deb =~ s/::/-/g;
+            eval { system "sudo apt-get install $deb" };
+            push @modules, $pkg, $ver if $@;
         }
     }
[download]

I bumped $VERSION in hope that system-wide version will be picked before local version in inc/ directory.

I would love to make this proper M::I module, but I'm afraid I don't have a clue where to start.